/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * vim: set ts=8 sts=4 et sw=4 tw=99: * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */#include"jit/IonAnalysis.h"#include"mozilla/SizePrintfMacros.h"#include"jit/AliasAnalysis.h"#include"jit/BaselineInspector.h"#include"jit/BaselineJIT.h"#include"jit/FlowAliasAnalysis.h"#include"jit/Ion.h"#include"jit/IonBuilder.h"#include"jit/IonOptimizationLevels.h"#include"jit/LIR.h"#include"jit/Lowering.h"#include"jit/MIRGraph.h"#include"vm/RegExpObject.h"#include"vm/SelfHosting.h"#include"jsobjinlines.h"#include"jsopcodeinlines.h"#include"jsscriptinlines.h"#include"jit/shared/Lowering-shared-inl.h"usingnamespacejs;usingnamespacejs::jit;usingmozilla::DebugOnly;typedefVector<MPhi*,16,SystemAllocPolicy>MPhiVector;staticboolFlagPhiInputsAsHavingRemovedUses(MIRGenerator*mir,MBasicBlock*block,MBasicBlock*succ,MPhiVector&worklist){// When removing an edge between 2 blocks, we might remove the ability of// later phases to figure out that the uses of a Phi should be considered as// a use of all its inputs. Thus we need to mark the Phi inputs as having// removed uses iff the phi has any uses.////// +--------------------+ +---------------------+// |12 MFoo 6 | |32 MBar 5 |// | | | |// | ... | | ... |// | | | |// |25 MGoto Block 4 | |43 MGoto Block 4 |// +--------------------+ +---------------------+// | |// | | |// | | |// | +-----X------------------------+// | Edge |// | Removed |// | |// | +------------v-----------+// | |50 MPhi 12 32 |// | | |// | | ... |// | | |// | |70 MReturn 50 |// | +------------------------+// |// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -// |// v//// ^ +--------------------+ +---------------------+// /!\ |12 MConst opt-out | |32 MBar 5 |// '---' | | | |// | ... | | ... |// |78 MBail | | |// |80 MUnreachable | |43 MGoto Block 4 |// +--------------------+ +---------------------+// |// |// |// +---------------+// |// |// |// +------------v-----------+// |50 MPhi 32 |// | |// | ... |// | |// |70 MReturn 50 |// +------------------------+////// If the inputs of the Phi are not flagged as having removed uses, then// later compilation phase might optimize them out. The problem is that a// bailout will use this value and give it back to baseline, which will then// use the OptimizedOut magic value in a computation.// Conservative upper limit for the number of Phi instructions which are// visited while looking for uses.constsize_tconservativeUsesLimit=128;MOZ_ASSERT(worklist.empty());size_tpredIndex=succ->getPredecessorIndex(block);MPhiIteratorend=succ->phisEnd();MPhiIteratorit=succ->phisBegin();for(;it!=end;it++){MPhi*phi=*it;if(mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses outer loop"))returnfalse;// We are looking to mark the Phi inputs which are used across the edge// between the |block| and its successor |succ|.MDefinition*def=phi->getOperand(predIndex);if(def->isUseRemoved())continue;phi->setInWorklist();if(!worklist.append(phi))returnfalse;// Fill the work list with all the Phi nodes uses until we reach either:// - A resume point which uses the Phi as an observable operand.// - An explicit use of the Phi instruction.// - An implicit use of the Phi instruction.boolisUsed=false;for(size_tidx=0;!isUsed&&idx<worklist.length();idx++){phi=worklist[idx];if(mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 1"))returnfalse;if(phi->isUseRemoved()||phi->isImplicitlyUsed()){// The phi is implicitly used.isUsed=true;break;}MUseIteratorusesEnd(phi->usesEnd());for(MUseIteratoruse(phi->usesBegin());use!=usesEnd;use++){MNode*consumer=(*use)->consumer();if(mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 2"))returnfalse;if(consumer->isResumePoint()){MResumePoint*rp=consumer->toResumePoint();if(rp->isObservableOperand(*use)){// The phi is observable via a resume point operand.isUsed=true;break;}continue;}MDefinition*cdef=consumer->toDefinition();if(!cdef->isPhi()){// The phi is explicitly used.isUsed=true;break;}phi=cdef->toPhi();if(phi->isInWorklist())continue;phi->setInWorklist();if(!worklist.append(phi))returnfalse;}// Use a conservative upper bound to avoid iterating too many times// on very large graphs.if(idx>=conservativeUsesLimit){isUsed=true;break;}}if(isUsed)def->setUseRemoved();// Remove all the InWorklist flags.while(!worklist.empty()){phi=worklist.popCopy();phi->setNotInWorklist();}}returntrue;}staticboolFlagAllOperandsAsHavingRemovedUses(MIRGenerator*mir,MBasicBlock*block){constCompileInfo&info=block->info();// Flag all instructions operands as having removed uses.MInstructionIteratorend=block->end();for(MInstructionIteratorit=block->begin();it!=end;it++){if(mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 1"))returnfalse;MInstruction*ins=*it;for(size_ti=0,e=ins->numOperands();i<e;i++)ins->getOperand(i)->setUseRemovedUnchecked();// Flag observable resume point operands as having removed uses.if(MResumePoint*rp=ins->resumePoint()){// Note: no need to iterate over the caller's of the resume point as// this is the same as the entry resume point.for(size_ti=0,e=rp->numOperands();i<e;i++){if(info.isObservableSlot(i))rp->getOperand(i)->setUseRemovedUnchecked();}}}// Flag observable operands of the entry resume point as having removed uses.MResumePoint*rp=block->entryResumePoint();while(rp){if(mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 2"))returnfalse;for(size_ti=0,e=rp->numOperands();i<e;i++){if(info.isObservableSlot(i))rp->getOperand(i)->setUseRemovedUnchecked();}rp=rp->caller();}// Flag Phi inputs of the successors has having removed uses.MPhiVectorworklist;for(size_ti=0,e=block->numSuccessors();i<e;i++){if(mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 3"))returnfalse;if(!FlagPhiInputsAsHavingRemovedUses(mir,block,block->getSuccessor(i),worklist))returnfalse;}returntrue;}staticvoidRemoveFromSuccessors(MBasicBlock*block){// Remove this block from its successors.size_tnumSucc=block->numSuccessors();while(numSucc--){MBasicBlock*succ=block->getSuccessor(numSucc);if(succ->isDead())continue;JitSpew(JitSpew_Prune,"Remove block edge %d -> %d.",block->id(),succ->id());succ->removePredecessor(block);}}staticvoidConvertToBailingBlock(TempAllocator&alloc,MBasicBlock*block){// Add a bailout instruction.MBail*bail=MBail::New(alloc,Bailout_FirstExecution);MInstruction*bailPoint=block->safeInsertTop();block->insertBefore(block->safeInsertTop(),bail);// Discard all remaining instructions.MInstructionIteratorclearStart=block->begin(bailPoint);block->discardAllInstructionsStartingAt(clearStart);if(block->outerResumePoint())block->clearOuterResumePoint();// And replace the last instruction by the unreachable control instruction.block->end(MUnreachable::New(alloc));}booljit::PruneUnusedBranches(MIRGenerator*mir,MIRGraph&graph){MOZ_ASSERT(!mir->compilingWasm(),"wasm compilation has no code coverage support.");// We do a reverse-post-order traversal, marking basic blocks when the block// have to be converted into bailing blocks, and flagging block as// unreachable if all predecessors are flagged as bailing or unreachable.boolsomeUnreachable=false;for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++){if(mir->shouldCancel("Prune unused branches (main loop)"))returnfalse;JitSpew(JitSpew_Prune,"Investigate Block %d:",block->id());JitSpewIndentindent(JitSpew_Prune);// Do not touch entry basic blocks.if(*block==graph.osrBlock()||*block==graph.entryBlock()){JitSpew(JitSpew_Prune,"Block %d is an entry point.",block->id());continue;}// Compute if all the predecessors of this block are either bailling out// or are already flagged as unreachable.boolisUnreachable=true;boolisLoopHeader=block->isLoopHeader();size_tnumPred=block->numPredecessors();size_ti=0;for(;i<numPred;i++){if(mir->shouldCancel("Prune unused branches (inner loop 1)"))returnfalse;MBasicBlock*pred=block->getPredecessor(i);// The backedge is visited after the loop header, but if the loop// header is unreachable, then we can assume that the backedge would// be unreachable too.if(isLoopHeader&&pred==block->backedge())continue;// Break if any of the predecessor can continue in this block.if(!pred->isMarked()&&!pred->unreachable()){isUnreachable=false;break;}}// Compute if the block should bailout, based on the trivial heuristic// which is that if the block never got visited before, then it is// likely to not be visited after.boolshouldBailout=block->getHitState()==MBasicBlock::HitState::Count&&block->getHitCount()==0;// Check if the predecessors got accessed a large number of times in// comparisons of the current block, in order to know if our attempt at// removing this block is not premature.if(!isUnreachable&&shouldBailout){size_tp=numPred;size_tpredCount=0;size_tnumSuccessorsOfPreds=1;boolisLoopExit=false;while(p--){if(mir->shouldCancel("Prune unused branches (inner loop 2)"))returnfalse;MBasicBlock*pred=block->getPredecessor(p);if(pred->getHitState()==MBasicBlock::HitState::Count)predCount+=pred->getHitCount();isLoopExit|=pred->isLoopHeader()&&pred->backedge()!=*block;numSuccessorsOfPreds+=pred->numSuccessors()-1;}// Iterate over the approximated set of dominated blocks and count// the number of instructions which are dominated. Note that this// approximation has issues with OSR blocks, but this should not be// a big deal.size_tnumDominatedInst=0;size_tnumEffectfulInst=0;intnumInOutEdges=block->numPredecessors();size_tbranchSpan=0;ReversePostorderIteratorit(block);do{if(mir->shouldCancel("Prune unused branches (inner loop 3)"))returnfalse;// Iterate over dominated blocks, and visit exit blocks as well.numInOutEdges-=it->numPredecessors();if(numInOutEdges<0)break;numInOutEdges+=it->numSuccessors();// Collect information about the instructions within the block.for(MDefinitionIteratordef(*it);def;def++){numDominatedInst++;if(def->isEffectful())numEffectfulInst++;}it++;branchSpan++;}while(numInOutEdges>0&&it!=graph.rpoEnd());// The goal of branch pruning is to remove branches which are// preventing other optimization, while keeping branches which would// be costly if we were to bailout. The following heuristics are// made to prevent bailouts in branches when we estimate that the// confidence is not enough to compensate for the cost of a bailout.//// 1. Confidence for removal varies with the number of hit counts// of the predecessor. The reason being that the likelyhood of// taking this branch is decreasing with the number of hit// counts of the predecessor.//// 2. Confidence for removal varies with the number of dominated// instructions. The reason being that the complexity of the// branch increases with the number of instructions, thus// working against other optimizations.//// 3. Confidence for removal varies with the span of the// branch. The reason being that a branch that spans over a// large set of blocks is likely to remove optimization// opportunity as it prevents instructions from the other// branches to dominate the blocks which are after.//// 4. Confidence for removal varies with the number of effectful// instructions. The reason being that an effectful instruction// can remove optimization opportunities based on Scalar// Replacement, and based on Alias Analysis.//// The following converts various units in some form of arbitrary// score, such that we can compare it to a threshold.size_tscore=0;MOZ_ASSERT(numSuccessorsOfPreds>=1);score+=predCount*JitOptions.branchPruningHitCountFactor/numSuccessorsOfPreds;score+=numDominatedInst*JitOptions.branchPruningInstFactor;score+=branchSpan*JitOptions.branchPruningBlockSpanFactor;score+=numEffectfulInst*JitOptions.branchPruningEffectfulInstFactor;if(score<JitOptions.branchPruningThreshold)shouldBailout=false;// If the predecessors do not have enough hit counts, keep the// branch, until we recompile this function later, with more// information.if(predCount/numSuccessorsOfPreds<50)shouldBailout=false;// There is only a single successors to the predecessors, thus the// decision should be taken as part of the previous block// investigation, and this block should be unreachable.if(numSuccessorsOfPreds==1)shouldBailout=false;// If this is the exit block of a loop, then keep this basic// block. This heuristic is useful as a bailout is often much more// costly than a simple exit sequence.if(isLoopExit)shouldBailout=false;// Interpreters are often implemented as a table switch within a for// loop. What might happen is that the interpreter heats up in a// subset of instructions, but might need other instructions for the// rest of the evaluation.if(numSuccessorsOfPreds>8)shouldBailout=false;JitSpew(JitSpew_Prune,"info: block %d,"" predCount: %"PRIuSIZE", domInst: %"PRIuSIZE", span: %"PRIuSIZE", effectful: %"PRIuSIZE", "" isLoopExit: %s, numSuccessorsOfPred: %"PRIuSIZE"."" (score: %"PRIuSIZE", shouldBailout: %s)",block->id(),predCount,numDominatedInst,branchSpan,numEffectfulInst,isLoopExit?"true":"false",numSuccessorsOfPreds,score,shouldBailout?"true":"false");}// Continue to the next basic block if the current basic block can// remain unchanged.if(!isUnreachable&&!shouldBailout)continue;someUnreachable=true;if(isUnreachable){JitSpew(JitSpew_Prune,"Mark block %d as unreachable.",block->id());block->setUnreachable();// If the block is unreachable, then there is no need to convert it// to a bailing block.}elseif(shouldBailout){JitSpew(JitSpew_Prune,"Mark block %d as bailing block.",block->id());block->markUnchecked();}// When removing a loop header, we should ensure that its backedge is// removed first, otherwise this triggers an assertion in// removePredecessorsWithoutPhiOperands.if(block->isLoopHeader()){JitSpew(JitSpew_Prune,"Mark block %d as bailing block. (loop backedge)",block->backedge()->id());block->backedge()->markUnchecked();}}// Returns early if nothing changed.if(!someUnreachable)returntrue;JitSpew(JitSpew_Prune,"Convert basic block to bailing blocks, and remove unreachable blocks:");JitSpewIndentindent(JitSpew_Prune);// As we are going to remove edges and basic block, we have to mark// instructions which would be needed by baseline if we were to bailout.for(PostorderIteratorit(graph.poBegin());it!=graph.poEnd();){if(mir->shouldCancel("Prune unused branches (marking loop)"))returnfalse;MBasicBlock*block=*it++;if(!block->isMarked()&&!block->unreachable())continue;FlagAllOperandsAsHavingRemovedUses(mir,block);}// Remove the blocks in post-order such that consumers are visited before// the predecessors, the only exception being the Phi nodes of loop headers.for(PostorderIteratorit(graph.poBegin());it!=graph.poEnd();){if(mir->shouldCancel("Prune unused branches (removal loop)"))returnfalse;MBasicBlock*block=*it++;if(!block->isMarked()&&!block->unreachable())continue;JitSpew(JitSpew_Prune,"Remove / Replace block %d.",block->id());JitSpewIndentindent(JitSpew_Prune);// As we are going to replace/remove the last instruction, we first have// to remove this block from the predecessor list of its successors.RemoveFromSuccessors(block);// Convert the current basic block to a bailing block which ends with an// Unreachable control instruction.if(block->isMarked()){JitSpew(JitSpew_Prune,"Convert Block %d to a bailing block.",block->id());if(!graph.alloc().ensureBallast())returnfalse;ConvertToBailingBlock(graph.alloc(),block);block->unmark();}// Remove all instructions.if(block->unreachable()){JitSpew(JitSpew_Prune,"Remove Block %d.",block->id());JitSpewIndentindent(JitSpew_Prune);graph.removeBlock(block);}}returntrue;}staticboolSplitCriticalEdgesForBlock(MIRGraph&graph,MBasicBlock*block){if(block->numSuccessors()<2)returntrue;for(size_ti=0;i<block->numSuccessors();i++){MBasicBlock*target=block->getSuccessor(i);if(target->numPredecessors()<2)continue;// Create a simple new block which contains a goto and which split the// edge between block and target.MBasicBlock*split=MBasicBlock::NewSplitEdge(graph,block,i,target);if(!split)returnfalse;}returntrue;}// A critical edge is an edge which is neither its successor's only predecessor// nor its predecessor's only successor. Critical edges must be split to// prevent copy-insertion and code motion from affecting other edges.booljit::SplitCriticalEdges(MIRGraph&graph){for(MBasicBlockIteratoriter(graph.begin());iter!=graph.end();iter++){MBasicBlock*block=*iter;if(!SplitCriticalEdgesForBlock(graph,block))returnfalse;}returntrue;}booljit::IsUint32Type(constMDefinition*def){if(def->isBeta())def=def->getOperand(0);if(def->type()!=MIRType::Int32)returnfalse;returndef->isUrsh()&&def->getOperand(1)->isConstant()&&def->getOperand(1)->toConstant()->type()==MIRType::Int32&&def->getOperand(1)->toConstant()->toInt32()==0;}// Return whether a block simply computes the specified constant value.staticboolBlockComputesConstant(MBasicBlock*block,MDefinition*value,bool*constBool){// Look for values with no uses. This is used to eliminate constant// computing blocks in condition statements, and the phi which used to// consume the constant has already been removed.if(value->hasUses())returnfalse;if(!value->isConstant()||value->block()!=block)returnfalse;if(!block->phisEmpty())returnfalse;for(MInstructionIteratoriter=block->begin();iter!=block->end();++iter){if(*iter!=value||!iter->isGoto())returnfalse;}returnvalue->toConstant()->valueToBoolean(constBool);}// Find phis that are redudant://// 1) phi(a, a)// can get replaced by a//// 2) phi(filtertypeset(a, type1), filtertypeset(a, type1))// equals filtertypeset(a, type1)//// 3) phi(a, filtertypeset(a, type1))// equals filtertypeset(a, type1 union type(a))// equals filtertypeset(a, type(a))// equals a//// 4) phi(filtertypeset(a, type1), filtertypeset(a, type2))// equals filtertypeset(a, type1 union type2)//// This is the special case. We can only replace this with 'a' iif// type(a) == type1 union type2. Since optimizations could have// happened based on a more specific phi type.staticboolIsPhiRedudantFilter(MPhi*phi){// Handle (1) and (2)if(phi->operandIfRedundant())returntrue;// Handle (3)boolonlyFilters=false;MDefinition*a=phi->getOperand(0);if(a->isFilterTypeSet()){a=a->toFilterTypeSet()->input();onlyFilters=true;}for(size_ti=1;i<phi->numOperands();i++){MDefinition*operand=phi->getOperand(i);if(operand==a){onlyFilters=false;continue;}if(operand->isFilterTypeSet()&&operand->toFilterTypeSet()->input()==a)continue;returnfalse;}if(!onlyFilters)returntrue;// Handle (4)MOZ_ASSERT(onlyFilters);returnEqualTypes(a->type(),a->resultTypeSet(),phi->type(),phi->resultTypeSet());}// Determine whether phiBlock/testBlock simply compute a phi and perform a// test on it.staticboolBlockIsSingleTest(MBasicBlock*phiBlock,MBasicBlock*testBlock,MPhi**pphi,MTest**ptest){*pphi=nullptr;*ptest=nullptr;if(phiBlock!=testBlock){MOZ_ASSERT(phiBlock->numSuccessors()==1&&phiBlock->getSuccessor(0)==testBlock);if(!phiBlock->begin()->isGoto())returnfalse;}MInstruction*ins=*testBlock->begin();if(!ins->isTest())returnfalse;MTest*test=ins->toTest();if(!test->input()->isPhi())returnfalse;MPhi*phi=test->input()->toPhi();if(phi->block()!=phiBlock)returnfalse;for(MUseIteratoriter=phi->usesBegin();iter!=phi->usesEnd();++iter){MUse*use=*iter;if(use->consumer()==test)continue;if(use->consumer()->isResumePoint()){MBasicBlock*useBlock=use->consumer()->block();if(useBlock==phiBlock||useBlock==testBlock)continue;}returnfalse;}for(MPhiIteratoriter=phiBlock->phisBegin();iter!=phiBlock->phisEnd();++iter){if(*iter==phi)continue;if(IsPhiRedudantFilter(*iter))continue;returnfalse;}if(phiBlock!=testBlock&&!testBlock->phisEmpty())returnfalse;*pphi=phi;*ptest=test;returntrue;}// Change block so that it ends in a goto to the specific target block.// existingPred is an existing predecessor of the block.staticvoidUpdateGotoSuccessor(TempAllocator&alloc,MBasicBlock*block,MBasicBlock*target,MBasicBlock*existingPred){MInstruction*ins=block->lastIns();MOZ_ASSERT(ins->isGoto());ins->toGoto()->target()->removePredecessor(block);block->discardLastIns();MGoto*newGoto=MGoto::New(alloc,target);block->end(newGoto);target->addPredecessorSameInputsAs(block,existingPred);}// Change block so that it ends in a test of the specified value, going to// either ifTrue or ifFalse. existingPred is an existing predecessor of ifTrue// or ifFalse with the same values incoming to ifTrue/ifFalse as block.// existingPred is not required to be a predecessor of ifTrue/ifFalse if block// already ends in a test going to that block on a true/false result.staticvoidUpdateTestSuccessors(TempAllocator&alloc,MBasicBlock*block,MDefinition*value,MBasicBlock*ifTrue,MBasicBlock*ifFalse,MBasicBlock*existingPred){MInstruction*ins=block->lastIns();if(ins->isTest()){MTest*test=ins->toTest();MOZ_ASSERT(test->input()==value);if(ifTrue!=test->ifTrue()){test->ifTrue()->removePredecessor(block);ifTrue->addPredecessorSameInputsAs(block,existingPred);MOZ_ASSERT(test->ifTrue()==test->getSuccessor(0));test->replaceSuccessor(0,ifTrue);}if(ifFalse!=test->ifFalse()){test->ifFalse()->removePredecessor(block);ifFalse->addPredecessorSameInputsAs(block,existingPred);MOZ_ASSERT(test->ifFalse()==test->getSuccessor(1));test->replaceSuccessor(1,ifFalse);}return;}MOZ_ASSERT(ins->isGoto());ins->toGoto()->target()->removePredecessor(block);block->discardLastIns();MTest*test=MTest::New(alloc,value,ifTrue,ifFalse);block->end(test);ifTrue->addPredecessorSameInputsAs(block,existingPred);ifFalse->addPredecessorSameInputsAs(block,existingPred);}staticboolMaybeFoldConditionBlock(MIRGraph&graph,MBasicBlock*initialBlock){// Optimize the MIR graph to improve the code generated for conditional// operations. A test like 'if (a ? b : c)' normally requires four blocks,// with a phi for the intermediate value. This can be improved to use three// blocks with no phi value, and if either b or c is constant,// e.g. 'if (a ? b : 0)', then the block associated with that constant// can be eliminated./* * Look for a diamond pattern: * * initialBlock * / \ * trueBranch falseBranch * \ / * phiBlock * | * testBlock * * Where phiBlock contains a single phi combining values pushed onto the * stack by trueBranch and falseBranch, and testBlock contains a test on * that phi. phiBlock and testBlock may be the same block; generated code * will use different blocks if the (?:) op is in an inlined function. */MInstruction*ins=initialBlock->lastIns();if(!ins->isTest())returntrue;MTest*initialTest=ins->toTest();MBasicBlock*trueBranch=initialTest->ifTrue();if(trueBranch->numPredecessors()!=1||trueBranch->numSuccessors()!=1)returntrue;MBasicBlock*falseBranch=initialTest->ifFalse();if(falseBranch->numPredecessors()!=1||falseBranch->numSuccessors()!=1)returntrue;MBasicBlock*phiBlock=trueBranch->getSuccessor(0);if(phiBlock!=falseBranch->getSuccessor(0))returntrue;if(phiBlock->numPredecessors()!=2)returntrue;if(initialBlock->isLoopBackedge()||trueBranch->isLoopBackedge()||falseBranch->isLoopBackedge())returntrue;MBasicBlock*testBlock=phiBlock;if(testBlock->numSuccessors()==1){if(testBlock->isLoopBackedge())returntrue;testBlock=testBlock->getSuccessor(0);if(testBlock->numPredecessors()!=1)returntrue;}// Make sure the test block does not have any outgoing loop backedges.if(!SplitCriticalEdgesForBlock(graph,testBlock))returnfalse;MPhi*phi;MTest*finalTest;if(!BlockIsSingleTest(phiBlock,testBlock,&phi,&finalTest))returntrue;MDefinition*trueResult=phi->getOperand(phiBlock->indexForPredecessor(trueBranch));MDefinition*falseResult=phi->getOperand(phiBlock->indexForPredecessor(falseBranch));// OK, we found the desired pattern, now transform the graph.// Patch up phis that filter their input.for(MPhiIteratoriter=phiBlock->phisBegin();iter!=phiBlock->phisEnd();++iter){if(*iter==phi)continue;MOZ_ASSERT(IsPhiRedudantFilter(*iter));MDefinition*redundant=(*iter)->operandIfRedundant();if(!redundant){redundant=(*iter)->getOperand(0);if(redundant->isFilterTypeSet())redundant=redundant->toFilterTypeSet()->input();}(*iter)->replaceAllUsesWith(redundant);}// Remove the phi from phiBlock.phiBlock->discardPhi(*phiBlock->phisBegin());// If either trueBranch or falseBranch just computes a constant for the// test, determine the block that branch will end up jumping to and eliminate// the branch. Otherwise, change the end of the block to a test that jumps// directly to successors of testBlock, rather than to testBlock itself.MBasicBlock*trueTarget=trueBranch;boolconstBool;if(BlockComputesConstant(trueBranch,trueResult,&constBool)){trueTarget=constBool?finalTest->ifTrue():finalTest->ifFalse();phiBlock->removePredecessor(trueBranch);graph.removeBlock(trueBranch);}elseif(initialTest->input()==trueResult){UpdateGotoSuccessor(graph.alloc(),trueBranch,finalTest->ifTrue(),testBlock);}else{UpdateTestSuccessors(graph.alloc(),trueBranch,trueResult,finalTest->ifTrue(),finalTest->ifFalse(),testBlock);}MBasicBlock*falseTarget=falseBranch;if(BlockComputesConstant(falseBranch,falseResult,&constBool)){falseTarget=constBool?finalTest->ifTrue():finalTest->ifFalse();phiBlock->removePredecessor(falseBranch);graph.removeBlock(falseBranch);}elseif(initialTest->input()==falseResult){UpdateGotoSuccessor(graph.alloc(),falseBranch,finalTest->ifFalse(),testBlock);}else{UpdateTestSuccessors(graph.alloc(),falseBranch,falseResult,finalTest->ifTrue(),finalTest->ifFalse(),testBlock);}// Short circuit the initial test to skip any constant branch eliminated above.UpdateTestSuccessors(graph.alloc(),initialBlock,initialTest->input(),trueTarget,falseTarget,testBlock);// Remove phiBlock, if different from testBlock.if(phiBlock!=testBlock){testBlock->removePredecessor(phiBlock);graph.removeBlock(phiBlock);}// Remove testBlock itself.finalTest->ifTrue()->removePredecessor(testBlock);finalTest->ifFalse()->removePredecessor(testBlock);graph.removeBlock(testBlock);returntrue;}booljit::FoldTests(MIRGraph&graph){for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){if(!MaybeFoldConditionBlock(graph,*block))returnfalse;}returntrue;}booljit::FoldEmptyBlocks(MIRGraph&graph){for(MBasicBlockIteratoriter(graph.begin());iter!=graph.end();){MBasicBlock*block=*iter;iter++;if(block->numPredecessors()!=1||block->numSuccessors()!=1)continue;if(!block->phisEmpty())continue;if(block->outerResumePoint())continue;if(*block->begin()!=*block->rbegin())continue;MBasicBlock*succ=block->getSuccessor(0);MBasicBlock*pred=block->getPredecessor(0);if(succ->numPredecessors()!=1)continue;size_tpos=pred->getSuccessorIndex(block);pred->lastIns()->replaceSuccessor(pos,succ);graph.removeBlock(block);succ->addPredecessorSameInputsAs(pred,block);succ->removePredecessor(block);}returntrue;}staticvoidEliminateTriviallyDeadResumePointOperands(MIRGraph&graph,MResumePoint*rp){// If we will pop the top of the stack immediately after resuming,// then don't preserve the top value in the resume point.if(rp->mode()!=MResumePoint::ResumeAt||*rp->pc()!=JSOP_POP)return;size_ttop=rp->stackDepth()-1;MOZ_ASSERT(!rp->isObservableOperand(top));MDefinition*def=rp->getOperand(top);if(def->isConstant())return;MConstant*constant=rp->block()->optimizedOutConstant(graph.alloc());rp->replaceOperand(top,constant);}// Operands to a resume point which are dead at the point of the resume can be// replaced with a magic value. This analysis supports limited detection of// dead operands, pruning those which are defined in the resume point's basic// block and have no uses outside the block or at points later than the resume// point.//// This is intended to ensure that extra resume points within a basic block// will not artificially extend the lifetimes of any SSA values. This could// otherwise occur if the new resume point captured a value which is created// between the old and new resume point and is dead at the new resume point.booljit::EliminateDeadResumePointOperands(MIRGenerator*mir,MIRGraph&graph){// If we are compiling try blocks, locals and arguments may be observable// from catch or finally blocks (which Ion does not compile). For now just// disable the pass in this case.if(graph.hasTryBlock())returntrue;for(PostorderIteratorblock=graph.poBegin();block!=graph.poEnd();block++){if(mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)"))returnfalse;if(MResumePoint*rp=block->entryResumePoint()){if(!graph.alloc().ensureBallast())returnfalse;EliminateTriviallyDeadResumePointOperands(graph,rp);}// The logic below can get confused on infinite loops.if(block->isLoopHeader()&&block->backedge()==*block)continue;for(MInstructionIteratorins=block->begin();ins!=block->end();ins++){if(MResumePoint*rp=ins->resumePoint()){if(!graph.alloc().ensureBallast())returnfalse;EliminateTriviallyDeadResumePointOperands(graph,rp);}// No benefit to replacing constant operands with other constants.if(ins->isConstant())continue;// Scanning uses does not give us sufficient information to tell// where instructions that are involved in box/unbox operations or// parameter passing might be live. Rewriting uses of these terms// in resume points may affect the interpreter's behavior. Rather// than doing a more sophisticated analysis, just ignore these.if(ins->isUnbox()||ins->isParameter()||ins->isTypeBarrier()||ins->isComputeThis()||ins->isFilterTypeSet()){continue;}// Early intermediate values captured by resume points, such as// TypedObject, ArrayState and its allocation, may be legitimately// dead in Ion code, but are still needed if we bail out. They can// recover on bailout.if(ins->isNewDerivedTypedObject()||ins->isRecoveredOnBailout()){MOZ_ASSERT(ins->canRecoverOnBailout());continue;}// If the instruction's behavior has been constant folded into a// separate instruction, we can't determine precisely where the// instruction becomes dead and can't eliminate its uses.if(ins->isImplicitlyUsed()||ins->isUseRemoved())continue;// Check if this instruction's result is only used within the// current block, and keep track of its last use in a definition// (not resume point). This requires the instructions in the block// to be numbered, ensured by running this immediately after alias// analysis.uint32_tmaxDefinition=0;for(MUseIteratoruses(ins->usesBegin());uses!=ins->usesEnd();uses++){MNode*consumer=uses->consumer();if(consumer->isResumePoint()){// If the instruction's is captured by one of the resume point, then// it might be observed indirectly while the frame is live on the// stack, so it has to be computed.MResumePoint*resume=consumer->toResumePoint();if(resume->isObservableOperand(*uses)){maxDefinition=UINT32_MAX;break;}continue;}MDefinition*def=consumer->toDefinition();if(def->block()!=*block||def->isBox()||def->isPhi()){maxDefinition=UINT32_MAX;break;}maxDefinition=Max(maxDefinition,def->id());}if(maxDefinition==UINT32_MAX)continue;// Walk the uses a second time, removing any in resume points after// the last use in a definition.for(MUseIteratoruses(ins->usesBegin());uses!=ins->usesEnd();){MUse*use=*uses++;if(use->consumer()->isDefinition())continue;MResumePoint*mrp=use->consumer()->toResumePoint();if(mrp->block()!=*block||!mrp->instruction()||mrp->instruction()==*ins||mrp->instruction()->id()<=maxDefinition){continue;}if(!graph.alloc().ensureBallast())returnfalse;// Store an optimized out magic value in place of all dead// resume point operands. Making any such substitution can in// general alter the interpreter's behavior, even though the// code is dead, as the interpreter will still execute opcodes// whose effects cannot be observed. If the magic value value// were to flow to, say, a dead property access the// interpreter could throw an exception; we avoid this problem// by removing dead operands before removing dead code.MConstant*constant=MConstant::New(graph.alloc(),MagicValue(JS_OPTIMIZED_OUT));block->insertBefore(*(block->begin()),constant);use->replaceProducer(constant);}}}returntrue;}// Test whether |def| would be needed if it had no uses.booljs::jit::DeadIfUnused(constMDefinition*def){return!def->isEffectful()&&(!def->isGuard()||def->block()==def->block()->graph().osrBlock())&&!def->isGuardRangeBailouts()&&!def->isControlInstruction()&&(!def->isInstruction()||!def->toInstruction()->resumePoint());}// Test whether |def| may be safely discarded, due to being dead or due to being// located in a basic block which has itself been marked for discarding.booljs::jit::IsDiscardable(constMDefinition*def){return!def->hasUses()&&(DeadIfUnused(def)||def->block()->isMarked());}// Instructions are useless if they are unused and have no side effects.// This pass eliminates useless instructions.// The graph itself is unchanged.booljit::EliminateDeadCode(MIRGenerator*mir,MIRGraph&graph){// Traverse in postorder so that we hit uses before definitions.// Traverse instruction list backwards for the same reason.for(PostorderIteratorblock=graph.poBegin();block!=graph.poEnd();block++){if(mir->shouldCancel("Eliminate Dead Code (main loop)"))returnfalse;// Remove unused instructions.for(MInstructionReverseIteratoriter=block->rbegin();iter!=block->rend();){MInstruction*inst=*iter++;if(js::jit::IsDiscardable(inst)){block->discard(inst);}}}returntrue;}staticinlineboolIsPhiObservable(MPhi*phi,Observabilityobserve){// If the phi has uses which are not reflected in SSA, then behavior in the// interpreter may be affected by removing the phi.if(phi->isImplicitlyUsed()||phi->isUseRemoved())returntrue;// Check for uses of this phi node outside of other phi nodes.// Note that, initially, we skip reading resume points, which we// don't count as actual uses. If the only uses are resume points,// then the SSA name is never consumed by the program. However,// after optimizations have been performed, it's possible that the// actual uses in the program have been (incorrectly) optimized// away, so we must be more conservative and consider resume// points as well.for(MUseIteratoriter(phi->usesBegin());iter!=phi->usesEnd();iter++){MNode*consumer=iter->consumer();if(consumer->isResumePoint()){MResumePoint*resume=consumer->toResumePoint();if(observe==ConservativeObservability)returntrue;if(resume->isObservableOperand(*iter))returntrue;}else{MDefinition*def=consumer->toDefinition();if(!def->isPhi())returntrue;}}returnfalse;}// Handles cases like:// x is phi(a, x) --> a// x is phi(a, a) --> astaticinlineMDefinition*IsPhiRedundant(MPhi*phi){MDefinition*first=phi->operandIfRedundant();if(first==nullptr)returnnullptr;// Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi.if(phi->isImplicitlyUsed())first->setImplicitlyUsedUnchecked();returnfirst;}booljit::EliminatePhis(MIRGenerator*mir,MIRGraph&graph,Observabilityobserve){// Eliminates redundant or unobservable phis from the graph. A// redundant phi is something like b = phi(a, a) or b = phi(a, b),// both of which can be replaced with a. An unobservable phi is// one that whose value is never used in the program.//// Note that we must be careful not to eliminate phis representing// values that the interpreter will require later. When the graph// is first constructed, we can be more aggressive, because there// is a greater correspondence between the CFG and the bytecode.// After optimizations such as GVN have been performed, however,// the bytecode and CFG may not correspond as closely to one// another. In that case, we must be more conservative. The flag// |conservativeObservability| is used to indicate that eliminate// phis is being run after some optimizations have been performed,// and thus we should use more conservative rules about// observability. The particular danger is that we can optimize// away uses of a phi because we think they are not executable,// but the foundation for that assumption is false TI information// that will eventually be invalidated. Therefore, if// |conservativeObservability| is set, we will consider any use// from a resume point to be observable. Otherwise, we demand a// use from an actual instruction.Vector<MPhi*,16,SystemAllocPolicy>worklist;// Add all observable phis to a worklist. We use the "in worklist" bit to// mean "this phi is live".for(PostorderIteratorblock=graph.poBegin();block!=graph.poEnd();block++){MPhiIteratoriter=block->phisBegin();while(iter!=block->phisEnd()){MPhi*phi=*iter++;if(mir->shouldCancel("Eliminate Phis (populate loop)"))returnfalse;// Flag all as unused, only observable phis would be marked as used// when processed by the work list.phi->setUnused();// If the phi is redundant, remove it here.if(MDefinition*redundant=IsPhiRedundant(phi)){phi->justReplaceAllUsesWith(redundant);block->discardPhi(phi);continue;}// Enqueue observable Phis.if(IsPhiObservable(phi,observe)){phi->setInWorklist();if(!worklist.append(phi))returnfalse;}}}// Iteratively mark all phis reachable from live phis.while(!worklist.empty()){if(mir->shouldCancel("Eliminate Phis (worklist)"))returnfalse;MPhi*phi=worklist.popCopy();MOZ_ASSERT(phi->isUnused());phi->setNotInWorklist();// The removal of Phis can produce newly redundant phis.if(MDefinition*redundant=IsPhiRedundant(phi)){// Add to the worklist the used phis which are impacted.for(MUseDefIteratorit(phi);it;it++){if(it.def()->isPhi()){MPhi*use=it.def()->toPhi();if(!use->isUnused()){use->setUnusedUnchecked();use->setInWorklist();if(!worklist.append(use))returnfalse;}}}phi->justReplaceAllUsesWith(redundant);}else{// Otherwise flag them as used.phi->setNotUnused();}// The current phi is/was used, so all its operands are used.for(size_ti=0,e=phi->numOperands();i<e;i++){MDefinition*in=phi->getOperand(i);if(!in->isPhi()||!in->isUnused()||in->isInWorklist())continue;in->setInWorklist();if(!worklist.append(in->toPhi()))returnfalse;}}// Sweep dead phis.for(PostorderIteratorblock=graph.poBegin();block!=graph.poEnd();block++){MPhiIteratoriter=block->phisBegin();while(iter!=block->phisEnd()){MPhi*phi=*iter++;if(phi->isUnused()){if(!phi->optimizeOutAllUses(graph.alloc()))returnfalse;block->discardPhi(phi);}}}returntrue;}namespace{// The type analysis algorithm inserts conversions and box/unbox instructions// to make the IR graph well-typed for future passes.//// Phi adjustment: If a phi's inputs are all the same type, the phi is// specialized to return that type.//// Input adjustment: Each input is asked to apply conversion operations to its// inputs. This may include Box, Unbox, or other instruction-specific type// conversion operations.//classTypeAnalyzer{MIRGenerator*mir;MIRGraph&graph;Vector<MPhi*,0,SystemAllocPolicy>phiWorklist_;TempAllocator&alloc()const{returngraph.alloc();}booladdPhiToWorklist(MPhi*phi){if(phi->isInWorklist())returntrue;if(!phiWorklist_.append(phi))returnfalse;phi->setInWorklist();returntrue;}MPhi*popPhi(){MPhi*phi=phiWorklist_.popCopy();phi->setNotInWorklist();returnphi;}boolrespecialize(MPhi*phi,MIRTypetype);boolpropagateSpecialization(MPhi*phi);boolspecializePhis();voidreplaceRedundantPhi(MPhi*phi);booladjustPhiInputs(MPhi*phi);booladjustInputs(MDefinition*def);boolinsertConversions();boolcheckFloatCoherency();boolgraphContainsFloat32();boolmarkPhiConsumers();boolmarkPhiProducers();boolspecializeValidFloatOps();booltryEmitFloatOperations();public:TypeAnalyzer(MIRGenerator*mir,MIRGraph&graph):mir(mir),graph(graph){}boolanalyze();};}/* anonymous namespace */// Try to specialize this phi based on its non-cyclic inputs.staticMIRTypeGuessPhiType(MPhi*phi,bool*hasInputsWithEmptyTypes){#ifdef DEBUG// Check that different magic constants aren't flowing together. Ignore// JS_OPTIMIZED_OUT, since an operand could be legitimately optimized// away.MIRTypemagicType=MIRType::None;for(size_ti=0;i<phi->numOperands();i++){MDefinition*in=phi->getOperand(i);if(in->type()==MIRType::MagicOptimizedArguments||in->type()==MIRType::MagicHole||in->type()==MIRType::MagicIsConstructing){if(magicType==MIRType::None)magicType=in->type();MOZ_ASSERT(magicType==in->type());}}#endif*hasInputsWithEmptyTypes=false;MIRTypetype=MIRType::None;boolconvertibleToFloat32=false;boolhasPhiInputs=false;for(size_ti=0,e=phi->numOperands();i<e;i++){MDefinition*in=phi->getOperand(i);if(in->isPhi()){hasPhiInputs=true;if(!in->toPhi()->triedToSpecialize())continue;if(in->type()==MIRType::None){// The operand is a phi we tried to specialize, but we were// unable to guess its type. propagateSpecialization will// propagate the type to this phi when it becomes known.continue;}}// Ignore operands which we've never observed.if(in->resultTypeSet()&&in->resultTypeSet()->empty()){*hasInputsWithEmptyTypes=true;continue;}if(type==MIRType::None){type=in->type();if(in->canProduceFloat32())convertibleToFloat32=true;continue;}if(type!=in->type()){if(convertibleToFloat32&&in->type()==MIRType::Float32){// If we only saw definitions that can be converted into Float32 before and// encounter a Float32 value, promote previous values to Float32type=MIRType::Float32;}elseif(IsTypeRepresentableAsDouble(type)&&IsTypeRepresentableAsDouble(in->type())){// Specialize phis with int32 and double operands as double.type=MIRType::Double;convertibleToFloat32&=in->canProduceFloat32();}else{returnMIRType::Value;}}}if(type==MIRType::None&&!hasPhiInputs){// All inputs are non-phis with empty typesets. Use MIRType::Value// in this case, as it's impossible to get better type information.MOZ_ASSERT(*hasInputsWithEmptyTypes);type=MIRType::Value;}returntype;}boolTypeAnalyzer::respecialize(MPhi*phi,MIRTypetype){if(phi->type()==type)returntrue;phi->specialize(type);returnaddPhiToWorklist(phi);}boolTypeAnalyzer::propagateSpecialization(MPhi*phi){MOZ_ASSERT(phi->type()!=MIRType::None);// Verify that this specialization matches any phis depending on it.for(MUseDefIteratoriter(phi);iter;iter++){if(!iter.def()->isPhi())continue;MPhi*use=iter.def()->toPhi();if(!use->triedToSpecialize())continue;if(use->type()==MIRType::None){// We tried to specialize this phi, but were unable to guess its// type. Now that we know the type of one of its operands, we can// specialize it.if(!respecialize(use,phi->type()))returnfalse;continue;}if(use->type()!=phi->type()){// Specialize phis with int32 that can be converted to float and float operands as floats.if((use->type()==MIRType::Int32&&use->canProduceFloat32()&&phi->type()==MIRType::Float32)||(phi->type()==MIRType::Int32&&phi->canProduceFloat32()&&use->type()==MIRType::Float32)){if(!respecialize(use,MIRType::Float32))returnfalse;continue;}// Specialize phis with int32 and double operands as double.if(IsTypeRepresentableAsDouble(use->type())&&IsTypeRepresentableAsDouble(phi->type())){if(!respecialize(use,MIRType::Double))returnfalse;continue;}// This phi in our use chain can now no longer be specialized.if(!respecialize(use,MIRType::Value))returnfalse;}}returntrue;}boolTypeAnalyzer::specializePhis(){Vector<MPhi*,0,SystemAllocPolicy>phisWithEmptyInputTypes;for(PostorderIteratorblock(graph.poBegin());block!=graph.poEnd();block++){if(mir->shouldCancel("Specialize Phis (main loop)"))returnfalse;for(MPhiIteratorphi(block->phisBegin());phi!=block->phisEnd();phi++){if(mir->shouldCancel("Specialize Phis (inner loop)"))returnfalse;boolhasInputsWithEmptyTypes;MIRTypetype=GuessPhiType(*phi,&hasInputsWithEmptyTypes);phi->specialize(type);if(type==MIRType::None){// We tried to guess the type but failed because all operands are// phis we still have to visit. Set the triedToSpecialize flag but// don't propagate the type to other phis, propagateSpecialization// will do that once we know the type of one of the operands.// Edge case: when this phi has a non-phi input with an empty// typeset, it's possible for two phis to have a cyclic// dependency and they will both have MIRType::None. Specialize// such phis to MIRType::Value later on.if(hasInputsWithEmptyTypes&&!phisWithEmptyInputTypes.append(*phi))returnfalse;continue;}if(!propagateSpecialization(*phi))returnfalse;}}do{while(!phiWorklist_.empty()){if(mir->shouldCancel("Specialize Phis (worklist)"))returnfalse;MPhi*phi=popPhi();if(!propagateSpecialization(phi))returnfalse;}// When two phis have a cyclic dependency and inputs that have an empty// typeset (which are ignored by GuessPhiType), we may still have to// specialize these to MIRType::Value.while(!phisWithEmptyInputTypes.empty()){if(mir->shouldCancel("Specialize Phis (phisWithEmptyInputTypes)"))returnfalse;MPhi*phi=phisWithEmptyInputTypes.popCopy();if(phi->type()==MIRType::None){phi->specialize(MIRType::Value);if(!propagateSpecialization(phi))returnfalse;}}}while(!phiWorklist_.empty());returntrue;}boolTypeAnalyzer::adjustPhiInputs(MPhi*phi){MIRTypephiType=phi->type();MOZ_ASSERT(phiType!=MIRType::None);// If we specialized a type that's not Value, there are 3 cases:// 1. Every input is of that type.// 2. Every observed input is of that type (i.e., some inputs haven't been executed yet).// 3. Inputs were doubles and int32s, and was specialized to double.if(phiType!=MIRType::Value){for(size_ti=0,e=phi->numOperands();i<e;i++){MDefinition*in=phi->getOperand(i);if(in->type()==phiType)continue;if(!alloc().ensureBallast())returnfalse;if(in->isBox()&&in->toBox()->input()->type()==phiType){phi->replaceOperand(i,in->toBox()->input());}else{MInstruction*replacement;if(phiType==MIRType::Double&&IsFloatType(in->type())){// Convert int32 operands to double.replacement=MToDouble::New(alloc(),in);}elseif(phiType==MIRType::Float32){if(in->type()==MIRType::Int32||in->type()==MIRType::Double){replacement=MToFloat32::New(alloc(),in);}else{// See comment belowif(in->type()!=MIRType::Value){MBox*box=MBox::New(alloc(),in);in->block()->insertBefore(in->block()->lastIns(),box);in=box;}MUnbox*unbox=MUnbox::New(alloc(),in,MIRType::Double,MUnbox::Fallible);in->block()->insertBefore(in->block()->lastIns(),unbox);replacement=MToFloat32::New(alloc(),in);}}else{// If we know this branch will fail to convert to phiType,// insert a box that'll immediately fail in the fallible unbox// below.if(in->type()!=MIRType::Value){MBox*box=MBox::New(alloc(),in);in->block()->insertBefore(in->block()->lastIns(),box);in=box;}// Be optimistic and insert unboxes when the operand is a// value.replacement=MUnbox::New(alloc(),in,phiType,MUnbox::Fallible);}in->block()->insertBefore(in->block()->lastIns(),replacement);phi->replaceOperand(i,replacement);}}returntrue;}// Box every typed input.for(size_ti=0,e=phi->numOperands();i<e;i++){MDefinition*in=phi->getOperand(i);if(in->type()==MIRType::Value)continue;// The input is being explicitly unboxed, so sneak past and grab// the original box.if(in->isUnbox()&&phi->typeIncludes(in->toUnbox()->input()))in=in->toUnbox()->input();if(in->type()!=MIRType::Value){if(!alloc().ensureBallast())returnfalse;MBasicBlock*pred=phi->block()->getPredecessor(i);in=AlwaysBoxAt(alloc(),pred->lastIns(),in);}phi->replaceOperand(i,in);}returntrue;}boolTypeAnalyzer::adjustInputs(MDefinition*def){// Definitions such as MPhi have no type policy.if(!def->isInstruction())returntrue;MInstruction*ins=def->toInstruction();TypePolicy*policy=ins->typePolicy();if(policy&&!policy->adjustInputs(alloc(),ins))returnfalse;returntrue;}voidTypeAnalyzer::replaceRedundantPhi(MPhi*phi){MBasicBlock*block=phi->block();js::Valuev;switch(phi->type()){caseMIRType::Undefined:v=UndefinedValue();break;caseMIRType::Null:v=NullValue();break;caseMIRType::MagicOptimizedArguments:v=MagicValue(JS_OPTIMIZED_ARGUMENTS);break;caseMIRType::MagicOptimizedOut:v=MagicValue(JS_OPTIMIZED_OUT);break;caseMIRType::MagicUninitializedLexical:v=MagicValue(JS_UNINITIALIZED_LEXICAL);break;default:MOZ_CRASH("unexpected type");}MConstant*c=MConstant::New(alloc(),v);// The instruction pass will insert the boxblock->insertBefore(*(block->begin()),c);phi->justReplaceAllUsesWith(c);}boolTypeAnalyzer::insertConversions(){// Instructions are processed in reverse postorder: all uses are defs are// seen before uses. This ensures that output adjustment (which may rewrite// inputs of uses) does not conflict with input adjustment.for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++){if(mir->shouldCancel("Insert Conversions"))returnfalse;for(MPhiIteratoriter(block->phisBegin()),end(block->phisEnd());iter!=end;){MPhi*phi=*iter++;if(phi->type()==MIRType::Undefined||phi->type()==MIRType::Null||phi->type()==MIRType::MagicOptimizedArguments||phi->type()==MIRType::MagicOptimizedOut||phi->type()==MIRType::MagicUninitializedLexical){replaceRedundantPhi(phi);block->discardPhi(phi);}else{if(!adjustPhiInputs(phi))returnfalse;}}// AdjustInputs can add/remove/mutate instructions before and after the// current instruction. Only increment the iterator after it is finished.for(MInstructionIteratoriter(block->begin());iter!=block->end();iter++){if(!alloc().ensureBallast())returnfalse;if(!adjustInputs(*iter))returnfalse;}}returntrue;}// This function tries to emit Float32 specialized operations whenever it's possible.// MIR nodes are flagged as:// - Producers, when they can create Float32 that might need to be coerced into a Double.// Loads in Float32 arrays and conversions to Float32 are producers.// - Consumers, when they can have Float32 as inputs and validate a legal use of a Float32.// Stores in Float32 arrays and conversions to Float32 are consumers.// - Float32 commutative, when using the Float32 instruction instead of the Double instruction// does not result in a compound loss of precision. This is the case for +, -, /, * with 2// operands, for instance. However, an addition with 3 operands is not commutative anymore,// so an intermediate coercion is needed.// Except for phis, all these flags are known after Ion building, so they cannot change during// the process.//// The idea behind the algorithm is easy: whenever we can prove that a commutative operation// has only producers as inputs and consumers as uses, we can specialize the operation as a// float32 operation. Otherwise, we have to convert all float32 inputs to doubles. Even// if a lot of conversions are produced, GVN will take care of eliminating the redundant ones.//// Phis have a special status. Phis need to be flagged as producers or consumers as they can// be inputs or outputs of commutative instructions. Fortunately, producers and consumers// properties are such that we can deduce the property using all non phis inputs first (which form// an initial phi graph) and then propagate all properties from one phi to another using a// fixed point algorithm. The algorithm is ensured to terminate as each iteration has less or as// many flagged phis as the previous iteration (so the worst steady state case is all phis being// flagged as false).//// In a nutshell, the algorithm applies three passes:// 1 - Determine which phis are consumers. Each phi gets an initial value by making a global AND on// all its non-phi inputs. Then each phi propagates its value to other phis. If after propagation,// the flag value changed, we have to reapply the algorithm on all phi operands, as a phi is a// consumer if all of its uses are consumers.// 2 - Determine which phis are producers. It's the same algorithm, except that we have to reapply// the algorithm on all phi uses, as a phi is a producer if all of its operands are producers.// 3 - Go through all commutative operations and ensure their inputs are all producers and their// uses are all consumers.boolTypeAnalyzer::markPhiConsumers(){MOZ_ASSERT(phiWorklist_.empty());// Iterate in postorder so worklist is initialized to RPO.for(PostorderIteratorblock(graph.poBegin());block!=graph.poEnd();++block){if(mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Initial state"))returnfalse;for(MPhiIteratorphi(block->phisBegin());phi!=block->phisEnd();++phi){MOZ_ASSERT(!phi->isInWorklist());boolcanConsumeFloat32=true;for(MUseDefIteratoruse(*phi);canConsumeFloat32&&use;use++){MDefinition*usedef=use.def();canConsumeFloat32&=usedef->isPhi()||usedef->canConsumeFloat32(use.use());}phi->setCanConsumeFloat32(canConsumeFloat32);if(canConsumeFloat32&&!addPhiToWorklist(*phi))returnfalse;}}while(!phiWorklist_.empty()){if(mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Fixed point"))returnfalse;MPhi*phi=popPhi();MOZ_ASSERT(phi->canConsumeFloat32(nullptr/* unused */));boolvalidConsumer=true;for(MUseDefIteratoruse(phi);use;use++){MDefinition*def=use.def();if(def->isPhi()&&!def->canConsumeFloat32(use.use())){validConsumer=false;break;}}if(validConsumer)continue;// Propagate invalidated phisphi->setCanConsumeFloat32(false);for(size_ti=0,e=phi->numOperands();i<e;++i){MDefinition*input=phi->getOperand(i);if(input->isPhi()&&!input->isInWorklist()&&input->canConsumeFloat32(nullptr/* unused */)){if(!addPhiToWorklist(input->toPhi()))returnfalse;}}}returntrue;}boolTypeAnalyzer::markPhiProducers(){MOZ_ASSERT(phiWorklist_.empty());// Iterate in reverse postorder so worklist is initialized to PO.for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();++block){if(mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - initial state"))returnfalse;for(MPhiIteratorphi(block->phisBegin());phi!=block->phisEnd();++phi){MOZ_ASSERT(!phi->isInWorklist());boolcanProduceFloat32=true;for(size_ti=0,e=phi->numOperands();canProduceFloat32&&i<e;++i){MDefinition*input=phi->getOperand(i);canProduceFloat32&=input->isPhi()||input->canProduceFloat32();}phi->setCanProduceFloat32(canProduceFloat32);if(canProduceFloat32&&!addPhiToWorklist(*phi))returnfalse;}}while(!phiWorklist_.empty()){if(mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - Fixed point"))returnfalse;MPhi*phi=popPhi();MOZ_ASSERT(phi->canProduceFloat32());boolvalidProducer=true;for(size_ti=0,e=phi->numOperands();i<e;++i){MDefinition*input=phi->getOperand(i);if(input->isPhi()&&!input->canProduceFloat32()){validProducer=false;break;}}if(validProducer)continue;// Propagate invalidated phisphi->setCanProduceFloat32(false);for(MUseDefIteratoruse(phi);use;use++){MDefinition*def=use.def();if(def->isPhi()&&!def->isInWorklist()&&def->canProduceFloat32()){if(!addPhiToWorklist(def->toPhi()))returnfalse;}}}returntrue;}boolTypeAnalyzer::specializeValidFloatOps(){for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();++block){if(mir->shouldCancel("Ensure Float32 commutativity - Instructions"))returnfalse;for(MInstructionIteratorins(block->begin());ins!=block->end();++ins){if(!ins->isFloat32Commutative())continue;if(ins->type()==MIRType::Float32)continue;if(!alloc().ensureBallast())returnfalse;// This call will try to specialize the instruction iff all uses are consumers and// all inputs are producers.ins->trySpecializeFloat32(alloc());}}returntrue;}boolTypeAnalyzer::graphContainsFloat32(){for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();++block){for(MDefinitionIteratordef(*block);def;def++){if(mir->shouldCancel("Ensure Float32 commutativity - Graph contains Float32"))returnfalse;if(def->type()==MIRType::Float32)returntrue;}}returnfalse;}boolTypeAnalyzer::tryEmitFloatOperations(){// Asm.js uses the ahead of time type checks to specialize operations, no need to check// them again at this point.if(mir->compilingWasm())returntrue;// Check ahead of time that there is at least one definition typed as Float32, otherwise we// don't need this pass.if(!graphContainsFloat32())returntrue;if(!markPhiConsumers())returnfalse;if(!markPhiProducers())returnfalse;if(!specializeValidFloatOps())returnfalse;returntrue;}boolTypeAnalyzer::checkFloatCoherency(){#ifdef DEBUG// Asserts that all Float32 instructions are flowing into Float32 consumers or specialized// operationsfor(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();++block){if(mir->shouldCancel("Check Float32 coherency"))returnfalse;for(MDefinitionIteratordef(*block);def;def++){if(def->type()!=MIRType::Float32)continue;for(MUseDefIteratoruse(*def);use;use++){MDefinition*consumer=use.def();MOZ_ASSERT(consumer->isConsistentFloat32Use(use.use()));}}}#endifreturntrue;}boolTypeAnalyzer::analyze(){if(!tryEmitFloatOperations())returnfalse;if(!specializePhis())returnfalse;if(!insertConversions())returnfalse;if(!checkFloatCoherency())returnfalse;returntrue;}booljit::ApplyTypeInformation(MIRGenerator*mir,MIRGraph&graph){TypeAnalyzeranalyzer(mir,graph);if(!analyzer.analyze())returnfalse;returntrue;}// Check if `def` is only the N-th operand of `useDef`.staticinlinesize_tIsExclusiveNthOperand(MDefinition*useDef,size_tn,MDefinition*def){uint32_tnum=useDef->numOperands();if(n>=num||useDef->getOperand(n)!=def)returnfalse;for(uint32_ti=0;i<num;i++){if(i==n)continue;if(useDef->getOperand(i)==def)returnfalse;}returntrue;}staticsize_tIsExclusiveThisArg(MCall*call,MDefinition*def){returnIsExclusiveNthOperand(call,MCall::IndexOfThis(),def);}staticsize_tIsExclusiveFirstArg(MCall*call,MDefinition*def){returnIsExclusiveNthOperand(call,MCall::IndexOfArgument(0),def);}staticboolIsRegExpHoistableCall(MCall*call,MDefinition*def){if(call->isConstructing())returnfalse;JSAtom*name;if(WrappedFunction*fun=call->getSingleTarget()){if(!fun->isSelfHostedBuiltin())returnfalse;name=GetSelfHostedFunctionName(fun->rawJSFunction());}else{MDefinition*funDef=call->getFunction();if(funDef->isDebugCheckSelfHosted())funDef=funDef->toDebugCheckSelfHosted()->input();if(funDef->isTypeBarrier())funDef=funDef->toTypeBarrier()->input();if(!funDef->isCallGetIntrinsicValue())returnfalse;name=funDef->toCallGetIntrinsicValue()->name();}// Hoistable only if the RegExp is the first argument of RegExpBuiltinExec.CompileRuntime*runtime=GetJitContext()->runtime;if(name==runtime->names().RegExpBuiltinExec||name==runtime->names().UnwrapAndCallRegExpBuiltinExec||name==runtime->names().RegExpMatcher||name==runtime->names().RegExpTester||name==runtime->names().RegExpSearcher){returnIsExclusiveFirstArg(call,def);}if(name==runtime->names().RegExp_prototype_Exec)returnIsExclusiveThisArg(call,def);returnfalse;}staticboolCanCompareRegExp(MCompare*compare,MDefinition*def){MDefinition*value;if(compare->lhs()==def){value=compare->rhs();}else{MOZ_ASSERT(compare->rhs()==def);value=compare->lhs();}// Comparing two regexp that weren't cloned will give different result// than if they were cloned.if(value->mightBeType(MIRType::Object))returnfalse;// Make sure @@toPrimitive is not called which could notice// the difference between a not cloned/cloned regexp.JSOpop=compare->jsop();// Strict equality comparison won't invoke @@toPrimitive.if(op==JSOP_STRICTEQ||op==JSOP_STRICTNE)returntrue;if(op!=JSOP_EQ&&op!=JSOP_NE){// Relational comparison always invoke @@toPrimitive.MOZ_ASSERT(op==JSOP_GT||op==JSOP_GE||op==JSOP_LT||op==JSOP_LE);returnfalse;}// Loose equality comparison can invoke @@toPrimitive.if(value->mightBeType(MIRType::Boolean)||value->mightBeType(MIRType::String)||value->mightBeType(MIRType::Int32)||value->mightBeType(MIRType::Double)||value->mightBeType(MIRType::Float32)||value->mightBeType(MIRType::Symbol)){returnfalse;}returntrue;}staticinlinevoidSetNotInWorklist(MDefinitionVector&worklist){for(size_ti=0;i<worklist.length();i++)worklist[i]->setNotInWorklist();}staticboolIsRegExpHoistable(MIRGenerator*mir,MDefinition*regexp,MDefinitionVector&worklist,bool*hoistable){MOZ_ASSERT(worklist.length()==0);if(!worklist.append(regexp))returnfalse;regexp->setInWorklist();for(size_ti=0;i<worklist.length();i++){MDefinition*def=worklist[i];if(mir->shouldCancel("IsRegExpHoistable outer loop"))returnfalse;for(MUseIteratoruse=def->usesBegin();use!=def->usesEnd();use++){if(mir->shouldCancel("IsRegExpHoistable inner loop"))returnfalse;// Ignore resume points. At this point all uses are listed.// No DCE or GVN or something has happened.if(use->consumer()->isResumePoint())continue;MDefinition*useDef=use->consumer()->toDefinition();// Step through a few white-listed ops.if(useDef->isPhi()||useDef->isFilterTypeSet()||useDef->isGuardShape()){if(useDef->isInWorklist())continue;if(!worklist.append(useDef))returnfalse;useDef->setInWorklist();continue;}// Instructions that doesn't invoke unknown code that may modify// RegExp instance or pass it to elsewhere.if(useDef->isRegExpMatcher()||useDef->isRegExpTester()||useDef->isRegExpSearcher()){if(IsExclusiveNthOperand(useDef,0,def))continue;}elseif(useDef->isLoadFixedSlot()||useDef->isTypeOf()){continue;}elseif(useDef->isCompare()){if(CanCompareRegExp(useDef->toCompare(),def))continue;}// Instructions that modifies `lastIndex` property.elseif(useDef->isStoreFixedSlot()){if(IsExclusiveNthOperand(useDef,0,def)){MStoreFixedSlot*store=useDef->toStoreFixedSlot();if(store->slot()==RegExpObject::lastIndexSlot())continue;}}elseif(useDef->isSetPropertyCache()){if(IsExclusiveNthOperand(useDef,0,def)){MSetPropertyCache*setProp=useDef->toSetPropertyCache();if(setProp->idval()->isConstant()){ValuepropIdVal=setProp->idval()->toConstant()->toJSValue();if(propIdVal.isString()){CompileRuntime*runtime=GetJitContext()->runtime;if(propIdVal.toString()==runtime->names().lastIndex)continue;}}}}// MCall is safe only for some known safe functions.elseif(useDef->isCall()){if(IsRegExpHoistableCall(useDef->toCall(),def))continue;}// Everything else is unsafe.SetNotInWorklist(worklist);worklist.clear();*hoistable=false;returntrue;}}SetNotInWorklist(worklist);worklist.clear();*hoistable=true;returntrue;}booljit::MakeMRegExpHoistable(MIRGenerator*mir,MIRGraph&graph){MDefinitionVectorworklist(graph.alloc());for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++){if(mir->shouldCancel("MakeMRegExpHoistable outer loop"))returnfalse;for(MDefinitionIteratoriter(*block);iter;iter++){if(!*iter)MOZ_CRASH("confirm bug 1263794.");if(mir->shouldCancel("MakeMRegExpHoistable inner loop"))returnfalse;if(!iter->isRegExp())continue;MRegExp*regexp=iter->toRegExp();boolhoistable=false;if(!IsRegExpHoistable(mir,regexp,worklist,&hoistable))returnfalse;if(!hoistable)continue;// Make MRegExp hoistableregexp->setMovable();regexp->setDoNotClone();// That would be incorrect for global/sticky, because lastIndex// could be wrong. Therefore setting the lastIndex to 0. That is// faster than a not movable regexp.RegExpObject*source=regexp->source();if(source->sticky()||source->global()){if(!graph.alloc().ensureBallast())returnfalse;MConstant*zero=MConstant::New(graph.alloc(),Int32Value(0));regexp->block()->insertAfter(regexp,zero);MStoreFixedSlot*lastIndex=MStoreFixedSlot::New(graph.alloc(),regexp,RegExpObject::lastIndexSlot(),zero);regexp->block()->insertAfter(zero,lastIndex);}}}returntrue;}voidjit::RenumberBlocks(MIRGraph&graph){size_tid=0;for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++)block->setId(id++);}// A utility for code which deletes blocks. Renumber the remaining blocks,// recompute dominators, and optionally recompute AliasAnalysis dependencies.booljit::AccountForCFGChanges(MIRGenerator*mir,MIRGraph&graph,boolupdateAliasAnalysis,boolunderValueNumberer){// Renumber the blocks and clear out the old dominator info.size_tid=0;for(ReversePostorderIteratori(graph.rpoBegin()),e(graph.rpoEnd());i!=e;++i){i->clearDominatorInfo();i->setId(id++);}// Recompute dominator info.if(!BuildDominatorTree(graph))returnfalse;// If needed, update alias analysis dependencies.if(updateAliasAnalysis){TraceLoggerThread*logger=TraceLoggerForCurrentThread();AutoTraceLoglog(logger,TraceLogger_AliasAnalysis);if(JitOptions.disableFlowAA){if(!AliasAnalysis(mir,graph).analyze())returnfalse;}else{if(!FlowAliasAnalysis(mir,graph).analyze())returnfalse;}}AssertExtendedGraphCoherency(graph,underValueNumberer);returntrue;}// Remove all blocks not marked with isMarked(). Unmark all remaining blocks.// Alias analysis dependencies may be invalid after calling this function.booljit::RemoveUnmarkedBlocks(MIRGenerator*mir,MIRGraph&graph,uint32_tnumMarkedBlocks){if(numMarkedBlocks==graph.numBlocks()){// If all blocks are marked, no blocks need removal. Just clear the// marks. We'll still need to update the dominator tree below though,// since we may have removed edges even if we didn't remove any blocks.graph.unmarkBlocks();}else{// As we are going to remove edges and basic blocks, we have to mark// instructions which would be needed by baseline if we were to// bailout.for(PostorderIteratorit(graph.poBegin());it!=graph.poEnd();){MBasicBlock*block=*it++;if(!block->isMarked())continue;FlagAllOperandsAsHavingRemovedUses(mir,block);}// Find unmarked blocks and remove them.for(ReversePostorderIteratoriter(graph.rpoBegin());iter!=graph.rpoEnd();){MBasicBlock*block=*iter++;if(block->isMarked()){block->unmark();continue;}// The block is unreachable. Clear out the loop header flag, as// we're doing the sweep of a mark-and-sweep here, so we no longer// need to worry about whether an unmarked block is a loop or not.if(block->isLoopHeader())block->clearLoopHeader();for(size_ti=0,e=block->numSuccessors();i!=e;++i)block->getSuccessor(i)->removePredecessor(block);graph.removeBlockIncludingPhis(block);}}// Renumber the blocks and update the dominator tree.returnAccountForCFGChanges(mir,graph,/*updateAliasAnalysis=*/false);}// A Simple, Fast Dominance Algorithm by Cooper et al.// Modified to support empty intersections for OSR, and in RPO.staticMBasicBlock*IntersectDominators(MBasicBlock*block1,MBasicBlock*block2){MBasicBlock*finger1=block1;MBasicBlock*finger2=block2;MOZ_ASSERT(finger1);MOZ_ASSERT(finger2);// In the original paper, the block ID comparisons are on the postorder index.// This implementation iterates in RPO, so the comparisons are reversed.// For this function to be called, the block must have multiple predecessors.// If a finger is then found to be self-dominating, it must therefore be// reachable from multiple roots through non-intersecting control flow.// nullptr is returned in this case, to denote an empty intersection.while(finger1->id()!=finger2->id()){while(finger1->id()>finger2->id()){MBasicBlock*idom=finger1->immediateDominator();if(idom==finger1)returnnullptr;// Empty intersection.finger1=idom;}while(finger2->id()>finger1->id()){MBasicBlock*idom=finger2->immediateDominator();if(idom==finger2)returnnullptr;// Empty intersection.finger2=idom;}}returnfinger1;}voidjit::ClearDominatorTree(MIRGraph&graph){for(MBasicBlockIteratoriter=graph.begin();iter!=graph.end();iter++)iter->clearDominatorInfo();}staticvoidComputeImmediateDominators(MIRGraph&graph){// The default start block is a root and therefore only self-dominates.MBasicBlock*startBlock=graph.entryBlock();startBlock->setImmediateDominator(startBlock);// Any OSR block is a root and therefore only self-dominates.MBasicBlock*osrBlock=graph.osrBlock();if(osrBlock)osrBlock->setImmediateDominator(osrBlock);boolchanged=true;while(changed){changed=false;ReversePostorderIteratorblock=graph.rpoBegin();// For each block in RPO, intersect all dominators.for(;block!=graph.rpoEnd();block++){// If a node has once been found to have no exclusive dominator,// it will never have an exclusive dominator, so it may be skipped.if(block->immediateDominator()==*block)continue;// A block with no predecessors is not reachable from any entry, so// it self-dominates.if(MOZ_UNLIKELY(block->numPredecessors()==0)){block->setImmediateDominator(*block);continue;}MBasicBlock*newIdom=block->getPredecessor(0);// Find the first common dominator.for(size_ti=1;i<block->numPredecessors();i++){MBasicBlock*pred=block->getPredecessor(i);if(pred->immediateDominator()==nullptr)continue;newIdom=IntersectDominators(pred,newIdom);// If there is no common dominator, the block self-dominates.if(newIdom==nullptr){block->setImmediateDominator(*block);changed=true;break;}}if(newIdom&&block->immediateDominator()!=newIdom){block->setImmediateDominator(newIdom);changed=true;}}}#ifdef DEBUG// Assert that all blocks have dominator information.for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){MOZ_ASSERT(block->immediateDominator()!=nullptr);}#endif}booljit::BuildDominatorTree(MIRGraph&graph){ComputeImmediateDominators(graph);Vector<MBasicBlock*,4,JitAllocPolicy>worklist(graph.alloc());// Traversing through the graph in post-order means that every non-phi use// of a definition is visited before the def itself. Since a def// dominates its uses, by the time we reach a particular// block, we have processed all of its dominated children, so// block->numDominated() is accurate.for(PostorderIteratori(graph.poBegin());i!=graph.poEnd();i++){MBasicBlock*child=*i;MBasicBlock*parent=child->immediateDominator();// Dominance is defined such that blocks always dominate themselves.child->addNumDominated(1);// If the block only self-dominates, it has no definite parent.// Add it to the worklist as a root for pre-order traversal.// This includes all roots. Order does not matter.if(child==parent){if(!worklist.append(child))returnfalse;continue;}if(!parent->addImmediatelyDominatedBlock(child))returnfalse;parent->addNumDominated(child->numDominated());}#ifdef DEBUG// If compiling with OSR, many blocks will self-dominate.// Without OSR, there is only one root block which dominates all.if(!graph.osrBlock())MOZ_ASSERT(graph.entryBlock()->numDominated()==graph.numBlocks());#endif// Now, iterate through the dominator tree in pre-order and annotate every// block with its index in the traversal.size_tindex=0;while(!worklist.empty()){MBasicBlock*block=worklist.popCopy();block->setDomIndex(index);if(!worklist.append(block->immediatelyDominatedBlocksBegin(),block->immediatelyDominatedBlocksEnd())){returnfalse;}index++;}returntrue;}booljit::BuildPhiReverseMapping(MIRGraph&graph){// Build a mapping such that given a basic block, whose successor has one or// more phis, we can find our specific input to that phi. To make this fast// mapping work we rely on a specific property of our structured control// flow graph: For a block with phis, its predecessors each have only one// successor with phis. Consider each case:// * Blocks with less than two predecessors cannot have phis.// * Breaks. A break always has exactly one successor, and the break// catch block has exactly one predecessor for each break, as// well as a final predecessor for the actual loop exit.// * Continues. A continue always has exactly one successor, and the// continue catch block has exactly one predecessor for each// continue, as well as a final predecessor for the actual// loop continuation. The continue itself has exactly one// successor.// * An if. Each branch as exactly one predecessor.// * A switch. Each branch has exactly one predecessor.// * Loop tail. A new block is always created for the exit, and if a// break statement is present, the exit block will forward// directly to the break block.for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){if(block->phisEmpty())continue;// Assert on the above.for(size_tj=0;j<block->numPredecessors();j++){MBasicBlock*pred=block->getPredecessor(j);#ifdef DEBUGsize_tnumSuccessorsWithPhis=0;for(size_tk=0;k<pred->numSuccessors();k++){MBasicBlock*successor=pred->getSuccessor(k);if(!successor->phisEmpty())numSuccessorsWithPhis++;}MOZ_ASSERT(numSuccessorsWithPhis<=1);#endifpred->setSuccessorWithPhis(*block,j);}}returntrue;}#ifdef DEBUGstaticboolCheckSuccessorImpliesPredecessor(MBasicBlock*A,MBasicBlock*B){// Assuming B = succ(A), verify A = pred(B).for(size_ti=0;i<B->numPredecessors();i++){if(A==B->getPredecessor(i))returntrue;}returnfalse;}staticboolCheckPredecessorImpliesSuccessor(MBasicBlock*A,MBasicBlock*B){// Assuming B = pred(A), verify A = succ(B).for(size_ti=0;i<B->numSuccessors();i++){if(A==B->getSuccessor(i))returntrue;}returnfalse;}// If you have issues with the usesBalance assertions, then define the macro// _DEBUG_CHECK_OPERANDS_USES_BALANCE to spew information on the error output.// This output can then be processed with the following awk script to filter and// highlight which checks are missing or if there is an unexpected operand /// use.//// define _DEBUG_CHECK_OPERANDS_USES_BALANCE 1/*$ ./js 2>stderr.log$ gawk ' /^==Check/ { context = ""; state = $2; } /^[a-z]/ { context = context "\n\t" $0; } /^==End/ { if (state == "Operand") { list[context] = list[context] - 1; } else if (state == "Use") { list[context] = list[context] + 1; } } END { for (ctx in list) { if (list[ctx] > 0) { print "Missing operand check", ctx, "\n" } if (list[ctx] < 0) { print "Missing use check", ctx, "\n" } }; }' < stderr.log*/staticvoidCheckOperand(constMNode*consumer,constMUse*use,int32_t*usesBalance){MOZ_ASSERT(use->hasProducer());MDefinition*producer=use->producer();MOZ_ASSERT(!producer->isDiscarded());MOZ_ASSERT(producer->block()!=nullptr);MOZ_ASSERT(use->consumer()==consumer);#ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCEFprinterprint(stderr);print.printf("==Check Operand\n");use->producer()->dump(print);print.printf(" index: %"PRIuSIZE"\n",use->consumer()->indexOf(use));use->consumer()->dump(print);print.printf("==End\n");#endif--*usesBalance;}staticvoidCheckUse(constMDefinition*producer,constMUse*use,int32_t*usesBalance){MOZ_ASSERT(!use->consumer()->block()->isDead());MOZ_ASSERT_IF(use->consumer()->isDefinition(),!use->consumer()->toDefinition()->isDiscarded());MOZ_ASSERT(use->consumer()->block()!=nullptr);MOZ_ASSERT(use->consumer()->getOperand(use->index())==producer);#ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCEFprinterprint(stderr);print.printf("==Check Use\n");use->producer()->dump(print);print.printf(" index: %"PRIuSIZE"\n",use->consumer()->indexOf(use));use->consumer()->dump(print);print.printf("==End\n");#endif++*usesBalance;}// To properly encode entry resume points, we have to ensure that all the// operands of the entry resume point are located before the safeInsertTop// location.staticvoidAssertOperandsBeforeSafeInsertTop(MResumePoint*resume){MBasicBlock*block=resume->block();if(block==block->graph().osrBlock())return;MInstruction*stop=block->safeInsertTop();for(size_ti=0,e=resume->numOperands();i<e;++i){MDefinition*def=resume->getOperand(i);if(def->block()!=block)continue;if(def->isPhi())continue;for(MInstructionIteratorins=block->begin();true;ins++){if(*ins==def)break;MOZ_ASSERT(*ins!=stop,"Resume point operand located after the safeInsertTop location");}}}#endif // DEBUGvoidjit::AssertBasicGraphCoherency(MIRGraph&graph,boolforce){#ifdef DEBUGif(!JitOptions.fullDebugChecks&&!force)return;MOZ_ASSERT(graph.entryBlock()->numPredecessors()==0);MOZ_ASSERT(graph.entryBlock()->phisEmpty());MOZ_ASSERT(!graph.entryBlock()->unreachable());if(MBasicBlock*osrBlock=graph.osrBlock()){MOZ_ASSERT(osrBlock->numPredecessors()==0);MOZ_ASSERT(osrBlock->phisEmpty());MOZ_ASSERT(osrBlock!=graph.entryBlock());MOZ_ASSERT(!osrBlock->unreachable());}if(MResumePoint*resumePoint=graph.entryResumePoint())MOZ_ASSERT(resumePoint->block()==graph.entryBlock());// Assert successor and predecessor list coherency.uint32_tcount=0;int32_tusesBalance=0;for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){count++;MOZ_ASSERT(&block->graph()==&graph);MOZ_ASSERT(!block->isDead());MOZ_ASSERT_IF(block->outerResumePoint()!=nullptr,block->entryResumePoint()!=nullptr);for(size_ti=0;i<block->numSuccessors();i++)MOZ_ASSERT(CheckSuccessorImpliesPredecessor(*block,block->getSuccessor(i)));for(size_ti=0;i<block->numPredecessors();i++)MOZ_ASSERT(CheckPredecessorImpliesSuccessor(*block,block->getPredecessor(i)));if(MResumePoint*resume=block->entryResumePoint()){MOZ_ASSERT(!resume->instruction());MOZ_ASSERT(resume->block()==*block);AssertOperandsBeforeSafeInsertTop(resume);}if(MResumePoint*resume=block->outerResumePoint()){MOZ_ASSERT(!resume->instruction());MOZ_ASSERT(resume->block()==*block);}for(MResumePointIteratoriter(block->resumePointsBegin());iter!=block->resumePointsEnd();iter++){// We cannot yet assert that is there is no instruction then this is// the entry resume point because we are still storing resume points// in the InlinePropertyTable.MOZ_ASSERT_IF(iter->instruction(),iter->instruction()->block()==*block);for(uint32_ti=0,e=iter->numOperands();i<e;i++)CheckOperand(*iter,iter->getUseFor(i),&usesBalance);}for(MPhiIteratorphi(block->phisBegin());phi!=block->phisEnd();phi++){MOZ_ASSERT(phi->numOperands()==block->numPredecessors());MOZ_ASSERT(!phi->isRecoveredOnBailout());MOZ_ASSERT(phi->type()!=MIRType::None);MOZ_ASSERT(phi->dependency()==nullptr);}for(MDefinitionIteratoriter(*block);iter;iter++){MOZ_ASSERT(iter->block()==*block);MOZ_ASSERT_IF(iter->hasUses(),iter->type()!=MIRType::None);MOZ_ASSERT(!iter->isDiscarded());MOZ_ASSERT_IF(iter->isStart(),*block==graph.entryBlock()||*block==graph.osrBlock());MOZ_ASSERT_IF(iter->isParameter(),*block==graph.entryBlock()||*block==graph.osrBlock());MOZ_ASSERT_IF(iter->isOsrEntry(),*block==graph.osrBlock());MOZ_ASSERT_IF(iter->isOsrValue(),*block==graph.osrBlock());// Assert that use chains are valid for this instruction.for(uint32_ti=0,end=iter->numOperands();i<end;i++)CheckOperand(*iter,iter->getUseFor(i),&usesBalance);for(MUseIteratoruse(iter->usesBegin());use!=iter->usesEnd();use++)CheckUse(*iter,*use,&usesBalance);if(iter->isInstruction()){if(MResumePoint*resume=iter->toInstruction()->resumePoint()){MOZ_ASSERT(resume->instruction()==*iter);MOZ_ASSERT(resume->block()==*block);MOZ_ASSERT(resume->block()->entryResumePoint()!=nullptr);}}if(iter->isRecoveredOnBailout())MOZ_ASSERT(!iter->hasLiveDefUses());}// The control instruction is not visited by the MDefinitionIterator.MControlInstruction*control=block->lastIns();MOZ_ASSERT(control->block()==*block);MOZ_ASSERT(!control->hasUses());MOZ_ASSERT(control->type()==MIRType::None);MOZ_ASSERT(!control->isDiscarded());MOZ_ASSERT(!control->isRecoveredOnBailout());MOZ_ASSERT(control->resumePoint()==nullptr);for(uint32_ti=0,end=control->numOperands();i<end;i++)CheckOperand(control,control->getUseFor(i),&usesBalance);for(size_ti=0;i<control->numSuccessors();i++)MOZ_ASSERT(control->getSuccessor(i));}// In case issues, see the _DEBUG_CHECK_OPERANDS_USES_BALANCE macro above.MOZ_ASSERT(usesBalance<=0,"More use checks than operand checks");MOZ_ASSERT(usesBalance>=0,"More operand checks than use checks");MOZ_ASSERT(graph.numBlocks()==count);#endif}#ifdef DEBUGstaticvoidAssertReversePostorder(MIRGraph&graph){// Check that every block is visited after all its predecessors (except backedges).for(ReversePostorderIteratoriter(graph.rpoBegin());iter!=graph.rpoEnd();++iter){MBasicBlock*block=*iter;MOZ_ASSERT(!block->isMarked());for(size_ti=0;i<block->numPredecessors();i++){MBasicBlock*pred=block->getPredecessor(i);if(!pred->isMarked()){MOZ_ASSERT(pred->isLoopBackedge());MOZ_ASSERT(block->backedge()==pred);}}block->mark();}graph.unmarkBlocks();}#endif#ifdef DEBUGstaticvoidAssertDominatorTree(MIRGraph&graph){// Check dominators.MOZ_ASSERT(graph.entryBlock()->immediateDominator()==graph.entryBlock());if(MBasicBlock*osrBlock=graph.osrBlock())MOZ_ASSERT(osrBlock->immediateDominator()==osrBlock);elseMOZ_ASSERT(graph.entryBlock()->numDominated()==graph.numBlocks());size_ti=graph.numBlocks();size_ttotalNumDominated=0;for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){MOZ_ASSERT(block->dominates(*block));MBasicBlock*idom=block->immediateDominator();MOZ_ASSERT(idom->dominates(*block));MOZ_ASSERT(idom==*block||idom->id()<block->id());if(idom==*block){totalNumDominated+=block->numDominated();}else{boolfoundInParent=false;for(size_tj=0;j<idom->numImmediatelyDominatedBlocks();j++){if(idom->getImmediatelyDominatedBlock(j)==*block){foundInParent=true;break;}}MOZ_ASSERT(foundInParent);}size_tnumDominated=1;for(size_tj=0;j<block->numImmediatelyDominatedBlocks();j++){MBasicBlock*dom=block->getImmediatelyDominatedBlock(j);MOZ_ASSERT(block->dominates(dom));MOZ_ASSERT(dom->id()>block->id());MOZ_ASSERT(dom->immediateDominator()==*block);numDominated+=dom->numDominated();}MOZ_ASSERT(block->numDominated()==numDominated);MOZ_ASSERT(block->numDominated()<=i);MOZ_ASSERT(block->numSuccessors()!=0||block->numDominated()==1);i--;}MOZ_ASSERT(i==0);MOZ_ASSERT(totalNumDominated==graph.numBlocks());}#endifvoidjit::AssertGraphCoherency(MIRGraph&graph,boolforce){#ifdef DEBUGif(!JitOptions.checkGraphConsistency)return;if(!JitOptions.fullDebugChecks&&!force)return;AssertBasicGraphCoherency(graph,force);AssertReversePostorder(graph);#endif}#ifdef DEBUGstaticboolIsResumableMIRType(MIRTypetype){// see CodeGeneratorShared::encodeAllocationswitch(type){caseMIRType::Undefined:caseMIRType::Null:caseMIRType::Boolean:caseMIRType::Int32:caseMIRType::Double:caseMIRType::Float32:caseMIRType::String:caseMIRType::Symbol:caseMIRType::Object:caseMIRType::MagicOptimizedArguments:caseMIRType::MagicOptimizedOut:caseMIRType::MagicUninitializedLexical:caseMIRType::MagicIsConstructing:caseMIRType::Value:caseMIRType::Int32x4:caseMIRType::Int16x8:caseMIRType::Int8x16:caseMIRType::Float32x4:caseMIRType::Bool32x4:caseMIRType::Bool16x8:caseMIRType::Bool8x16:returntrue;caseMIRType::MagicHole:caseMIRType::ObjectOrNull:caseMIRType::None:caseMIRType::Slots:caseMIRType::Elements:caseMIRType::Pointer:caseMIRType::Shape:caseMIRType::ObjectGroup:caseMIRType::Doublex2:// NYI, see also RSimdBox::recovercaseMIRType::SinCosDouble:caseMIRType::Int64:returnfalse;}MOZ_CRASH("Unknown MIRType.");}staticvoidAssertResumableOperands(MNode*node){for(size_ti=0,e=node->numOperands();i<e;++i){MDefinition*op=node->getOperand(i);if(op->isRecoveredOnBailout())continue;MOZ_ASSERT(IsResumableMIRType(op->type()),"Resume point cannot encode its operands");}}staticvoidAssertIfResumableInstruction(MDefinition*def){if(!def->isRecoveredOnBailout())return;AssertResumableOperands(def);}staticvoidAssertResumePointDominatedByOperands(MResumePoint*resume){for(size_ti=0,e=resume->numOperands();i<e;++i){MDefinition*op=resume->getOperand(i);if(op->type()==MIRType::MagicOptimizedArguments)continue;MOZ_ASSERT(op->block()->dominates(resume->block()),"Resume point is not dominated by its operands");}}#endif // DEBUGvoidjit::AssertExtendedGraphCoherency(MIRGraph&graph,boolunderValueNumberer,boolforce){// Checks the basic GraphCoherency but also other conditions that// do not hold immediately (such as the fact that critical edges// are split)#ifdef DEBUGif(!JitOptions.checkGraphConsistency)return;if(!JitOptions.fullDebugChecks&&!force)return;AssertGraphCoherency(graph,force);AssertDominatorTree(graph);DebugOnly<uint32_t>idx=0;for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){MOZ_ASSERT(block->id()==idx);++idx;// No critical edges:if(block->numSuccessors()>1)for(size_ti=0;i<block->numSuccessors();i++)MOZ_ASSERT(block->getSuccessor(i)->numPredecessors()==1);if(block->isLoopHeader()){if(underValueNumberer&&block->numPredecessors()==3){// Fixup block.MOZ_ASSERT(block->getPredecessor(1)->numPredecessors()==0);MOZ_ASSERT(graph.osrBlock(),"Fixup blocks should only exists if we have an osr block.");}else{MOZ_ASSERT(block->numPredecessors()==2);}MBasicBlock*backedge=block->backedge();MOZ_ASSERT(backedge->id()>=block->id());MOZ_ASSERT(backedge->numSuccessors()==1);MOZ_ASSERT(backedge->getSuccessor(0)==*block);}if(!block->phisEmpty()){for(size_ti=0;i<block->numPredecessors();i++){MBasicBlock*pred=block->getPredecessor(i);MOZ_ASSERT(pred->successorWithPhis()==*block);MOZ_ASSERT(pred->positionInPhiSuccessor()==i);}}uint32_tsuccessorWithPhis=0;for(size_ti=0;i<block->numSuccessors();i++)if(!block->getSuccessor(i)->phisEmpty())successorWithPhis++;MOZ_ASSERT(successorWithPhis<=1);MOZ_ASSERT((successorWithPhis!=0)==(block->successorWithPhis()!=nullptr));// Verify that phi operands dominate the corresponding CFG predecessor// edges.for(MPhiIteratoriter(block->phisBegin()),end(block->phisEnd());iter!=end;++iter){MPhi*phi=*iter;for(size_ti=0,e=phi->numOperands();i<e;++i){MOZ_ASSERT(phi->getOperand(i)->block()->dominates(block->getPredecessor(i)),"Phi input is not dominated by its operand");}}// Verify that instructions are dominated by their operands.for(MInstructionIteratoriter(block->begin()),end(block->end());iter!=end;++iter){MInstruction*ins=*iter;for(size_ti=0,e=ins->numOperands();i<e;++i){MDefinition*op=ins->getOperand(i);MBasicBlock*opBlock=op->block();MOZ_ASSERT(opBlock->dominates(*block),"Instruction is not dominated by its operands");// If the operand is an instruction in the same block, check// that it comes first.if(opBlock==*block&&!op->isPhi()){MInstructionIteratoropIter=block->begin(op->toInstruction());do{++opIter;MOZ_ASSERT(opIter!=block->end(),"Operand in same block as instruction does not precede");}while(*opIter!=ins);}}AssertIfResumableInstruction(ins);if(MResumePoint*resume=ins->resumePoint()){AssertResumePointDominatedByOperands(resume);AssertResumableOperands(resume);}}// Verify that the block resume points are dominated by their operands.if(MResumePoint*resume=block->entryResumePoint()){AssertResumePointDominatedByOperands(resume);AssertResumableOperands(resume);}if(MResumePoint*resume=block->outerResumePoint()){AssertResumePointDominatedByOperands(resume);AssertResumableOperands(resume);}}#endif}structBoundsCheckInfo{MBoundsCheck*check;uint32_tvalidEnd;};typedefHashMap<uint32_t,BoundsCheckInfo,DefaultHasher<uint32_t>,JitAllocPolicy>BoundsCheckMap;// Compute a hash for bounds checks which ignores constant offsets in the index.staticHashNumberBoundsCheckHashIgnoreOffset(MBoundsCheck*check){SimpleLinearSumindexSum=ExtractLinearSum(check->index());uintptr_tindex=indexSum.term?uintptr_t(indexSum.term):0;uintptr_tlength=uintptr_t(check->length());returnindex^length;}staticMBoundsCheck*FindDominatingBoundsCheck(BoundsCheckMap&checks,MBoundsCheck*check,size_tindex){// Since we are traversing the dominator tree in pre-order, when we// are looking at the |index|-th block, the next numDominated() blocks// we traverse are precisely the set of blocks that are dominated.//// So, this value is visible in all blocks if:// index <= index + ins->block->numDominated()// and becomes invalid after that.HashNumberhash=BoundsCheckHashIgnoreOffset(check);BoundsCheckMap::Ptrp=checks.lookup(hash);if(!p||index>=p->value().validEnd){// We didn't find a dominating bounds check.BoundsCheckInfoinfo;info.check=check;info.validEnd=index+check->block()->numDominated();if(!checks.put(hash,info))returnnullptr;returncheck;}returnp->value().check;}staticMathSpaceExtractMathSpace(MDefinition*ins){MOZ_ASSERT(ins->isAdd()||ins->isSub());MBinaryArithInstruction*arith=nullptr;if(ins->isAdd())arith=ins->toAdd();elsearith=ins->toSub();switch(arith->truncateKind()){caseMDefinition::NoTruncate:caseMDefinition::TruncateAfterBailouts:// TruncateAfterBailouts is considered as infinite space because the// LinearSum will effectively remove the bailout check.returnMathSpace::Infinite;caseMDefinition::IndirectTruncate:caseMDefinition::Truncate:returnMathSpace::Modulo;}MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE("Unknown TruncateKind");}// Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0').SimpleLinearSumjit::ExtractLinearSum(MDefinition*ins,MathSpacespace){if(ins->isBeta())ins=ins->getOperand(0);if(ins->type()!=MIRType::Int32)returnSimpleLinearSum(ins,0);if(ins->isConstant())returnSimpleLinearSum(nullptr,ins->toConstant()->toInt32());if(!ins->isAdd()&&!ins->isSub())returnSimpleLinearSum(ins,0);// Only allow math which are in the same space.MathSpaceinsSpace=ExtractMathSpace(ins);if(space==MathSpace::Unknown)space=insSpace;elseif(space!=insSpace)returnSimpleLinearSum(ins,0);MOZ_ASSERT(space==MathSpace::Modulo||space==MathSpace::Infinite);MDefinition*lhs=ins->getOperand(0);MDefinition*rhs=ins->getOperand(1);if(lhs->type()!=MIRType::Int32||rhs->type()!=MIRType::Int32)returnSimpleLinearSum(ins,0);// Extract linear sums of each operand.SimpleLinearSumlsum=ExtractLinearSum(lhs,space);SimpleLinearSumrsum=ExtractLinearSum(rhs,space);// LinearSum only considers a single term operand, if both sides have// terms, then ignore extracted linear sums.if(lsum.term&&rsum.term)returnSimpleLinearSum(ins,0);// Check if this is of the form <SUM> + n or n + <SUM>.if(ins->isAdd()){int32_tconstant;if(space==MathSpace::Modulo)constant=lsum.constant+rsum.constant;elseif(!SafeAdd(lsum.constant,rsum.constant,&constant))returnSimpleLinearSum(ins,0);returnSimpleLinearSum(lsum.term?lsum.term:rsum.term,constant);}MOZ_ASSERT(ins->isSub());// Check if this is of the form <SUM> - n.if(lsum.term){int32_tconstant;if(space==MathSpace::Modulo)constant=lsum.constant-rsum.constant;elseif(!SafeSub(lsum.constant,rsum.constant,&constant))returnSimpleLinearSum(ins,0);returnSimpleLinearSum(lsum.term,constant);}// Ignore any of the form n - <SUM>.returnSimpleLinearSum(ins,0);}// Extract a linear inequality holding when a boolean test goes in the// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).booljit::ExtractLinearInequality(MTest*test,BranchDirectiondirection,SimpleLinearSum*plhs,MDefinition**prhs,bool*plessEqual){if(!test->getOperand(0)->isCompare())returnfalse;MCompare*compare=test->getOperand(0)->toCompare();MDefinition*lhs=compare->getOperand(0);MDefinition*rhs=compare->getOperand(1);// TODO: optimize Compare_UInt32if(!compare->isInt32Comparison())returnfalse;MOZ_ASSERT(lhs->type()==MIRType::Int32);MOZ_ASSERT(rhs->type()==MIRType::Int32);JSOpjsop=compare->jsop();if(direction==FALSE_BRANCH)jsop=NegateCompareOp(jsop);SimpleLinearSumlsum=ExtractLinearSum(lhs);SimpleLinearSumrsum=ExtractLinearSum(rhs);if(!SafeSub(lsum.constant,rsum.constant,&lsum.constant))returnfalse;// Normalize operations to use <= or >=.switch(jsop){caseJSOP_LE:*plessEqual=true;break;caseJSOP_LT:/* x < y ==> x + 1 <= y */if(!SafeAdd(lsum.constant,1,&lsum.constant))returnfalse;*plessEqual=true;break;caseJSOP_GE:*plessEqual=false;break;caseJSOP_GT:/* x > y ==> x - 1 >= y */if(!SafeSub(lsum.constant,1,&lsum.constant))returnfalse;*plessEqual=false;break;default:returnfalse;}*plhs=lsum;*prhs=rsum.term;returntrue;}staticboolTryEliminateBoundsCheck(BoundsCheckMap&checks,size_tblockIndex,MBoundsCheck*dominated,bool*eliminated){MOZ_ASSERT(!*eliminated);// Replace all uses of the bounds check with the actual index.// This is (a) necessary, because we can coalesce two different// bounds checks and would otherwise use the wrong index and// (b) helps register allocation. Note that this is safe since// no other pass after bounds check elimination moves instructions.dominated->replaceAllUsesWith(dominated->index());if(!dominated->isMovable())returntrue;if(!dominated->fallible())returntrue;MBoundsCheck*dominating=FindDominatingBoundsCheck(checks,dominated,blockIndex);if(!dominating)returnfalse;if(dominating==dominated){// We didn't find a dominating bounds check.returntrue;}// We found two bounds checks with the same hash number, but we still have// to make sure the lengths and index terms are equal.if(dominating->length()!=dominated->length())returntrue;SimpleLinearSumsumA=ExtractLinearSum(dominating->index());SimpleLinearSumsumB=ExtractLinearSum(dominated->index());// Both terms should be nullptr or the same definition.if(sumA.term!=sumB.term)returntrue;// This bounds check is redundant.*eliminated=true;// Normalize the ranges according to the constant offsets in the two indexes.int32_tminimumA,maximumA,minimumB,maximumB;if(!SafeAdd(sumA.constant,dominating->minimum(),&minimumA)||!SafeAdd(sumA.constant,dominating->maximum(),&maximumA)||!SafeAdd(sumB.constant,dominated->minimum(),&minimumB)||!SafeAdd(sumB.constant,dominated->maximum(),&maximumB)){returnfalse;}// Update the dominating check to cover both ranges, denormalizing the// result per the constant offset in the index.int32_tnewMinimum,newMaximum;if(!SafeSub(Min(minimumA,minimumB),sumA.constant,&newMinimum)||!SafeSub(Max(maximumA,maximumB),sumA.constant,&newMaximum)){returnfalse;}dominating->setMinimum(newMinimum);dominating->setMaximum(newMaximum);returntrue;}staticvoidTryEliminateTypeBarrierFromTest(MTypeBarrier*barrier,boolfiltersNull,boolfiltersUndefined,MTest*test,BranchDirectiondirection,bool*eliminated){MOZ_ASSERT(filtersNull||filtersUndefined);// Watch for code patterns similar to 'if (x.f) { ... = x.f }'. If x.f// is either an object or null/undefined, there will be a type barrier on// the latter read as the null/undefined value is never realized there.// The type barrier can be eliminated, however, by looking at tests// performed on the result of the first operation that filter out all// types that have been seen in the first access but not the second.// A test 'if (x.f)' filters both null and undefined.// Disregard the possible unbox added before the Typebarrier for checking.MDefinition*input=barrier->input();MUnbox*inputUnbox=nullptr;if(input->isUnbox()&&input->toUnbox()->mode()!=MUnbox::Fallible){inputUnbox=input->toUnbox();input=inputUnbox->input();}MDefinition*subject=nullptr;boolremoveUndefined;boolremoveNull;test->filtersUndefinedOrNull(direction==TRUE_BRANCH,&subject,&removeUndefined,&removeNull);// The Test doesn't filter undefined nor null.if(!subject)return;// Make sure the subject equals the input to the TypeBarrier.if(subject!=input)return;// When the TypeBarrier filters undefined, the test must at least also do,// this, before the TypeBarrier can get removed.if(!removeUndefined&&filtersUndefined)return;// When the TypeBarrier filters null, the test must at least also do,// this, before the TypeBarrier can get removed.if(!removeNull&&filtersNull)return;// Eliminate the TypeBarrier. The possible TypeBarrier unboxing is kept,// but made infallible.*eliminated=true;if(inputUnbox)inputUnbox->makeInfallible();barrier->replaceAllUsesWith(barrier->input());}staticboolTryEliminateTypeBarrier(MTypeBarrier*barrier,bool*eliminated){MOZ_ASSERT(!*eliminated);constTemporaryTypeSet*barrierTypes=barrier->resultTypeSet();constTemporaryTypeSet*inputTypes=barrier->input()->resultTypeSet();// Disregard the possible unbox added before the Typebarrier.if(barrier->input()->isUnbox()&&barrier->input()->toUnbox()->mode()!=MUnbox::Fallible)inputTypes=barrier->input()->toUnbox()->input()->resultTypeSet();if(!barrierTypes||!inputTypes)returntrue;boolfiltersNull=barrierTypes->filtersType(inputTypes,TypeSet::NullType());boolfiltersUndefined=barrierTypes->filtersType(inputTypes,TypeSet::UndefinedType());if(!filtersNull&&!filtersUndefined)returntrue;MBasicBlock*block=barrier->block();while(true){BranchDirectiondirection;MTest*test=block->immediateDominatorBranch(&direction);if(test){TryEliminateTypeBarrierFromTest(barrier,filtersNull,filtersUndefined,test,direction,eliminated);}MBasicBlock*previous=block->immediateDominator();if(previous==block)break;block=previous;}returntrue;}staticboolTryOptimizeLoadObjectOrNull(MDefinition*def,MDefinitionVector*peliminateList){if(def->type()!=MIRType::Value)returntrue;// Check if this definition can only produce object or null values.TemporaryTypeSet*types=def->resultTypeSet();if(!types)returntrue;if(types->baseFlags()&~(TYPE_FLAG_NULL|TYPE_FLAG_ANYOBJECT))returntrue;MDefinitionVectoreliminateList(def->block()->graph().alloc());for(MUseDefIteratoriter(def);iter;++iter){MDefinition*ndef=iter.def();switch(ndef->op()){caseMDefinition::Op_Compare:if(ndef->toCompare()->compareType()!=MCompare::Compare_Null)returntrue;break;caseMDefinition::Op_Test:break;caseMDefinition::Op_PostWriteBarrier:break;caseMDefinition::Op_StoreFixedSlot:break;caseMDefinition::Op_StoreSlot:break;caseMDefinition::Op_ToObjectOrNull:if(!eliminateList.append(ndef->toToObjectOrNull()))returnfalse;break;caseMDefinition::Op_Unbox:if(ndef->type()!=MIRType::Object)returntrue;break;caseMDefinition::Op_TypeBarrier:// For now, only handle type barriers which are not consumed// anywhere and only test that the value is null.if(ndef->hasUses()||ndef->resultTypeSet()->getKnownMIRType()!=MIRType::Null)returntrue;break;default:returntrue;}}// On punboxing systems we are better off leaving the value boxed if it// is only stored back to the heap.#ifdef JS_PUNBOX64boolfoundUse=false;for(MUseDefIteratoriter(def);iter;++iter){MDefinition*ndef=iter.def();if(!ndef->isStoreFixedSlot()&&!ndef->isStoreSlot()){foundUse=true;break;}}if(!foundUse)returntrue;#endif // JS_PUNBOX64def->setResultType(MIRType::ObjectOrNull);// Fixup the result type of MTypeBarrier uses.for(MUseDefIteratoriter(def);iter;++iter){MDefinition*ndef=iter.def();if(ndef->isTypeBarrier())ndef->setResultType(MIRType::ObjectOrNull);}// Eliminate MToObjectOrNull instruction uses.for(size_ti=0;i<eliminateList.length();i++){MDefinition*ndef=eliminateList[i];ndef->replaceAllUsesWith(def);if(!peliminateList->append(ndef))returnfalse;}returntrue;}staticinlineMDefinition*PassthroughOperand(MDefinition*def){if(def->isConvertElementsToDoubles())returndef->toConvertElementsToDoubles()->elements();if(def->isMaybeCopyElementsForWrite())returndef->toMaybeCopyElementsForWrite()->object();if(def->isConvertUnboxedObjectToNative())returndef->toConvertUnboxedObjectToNative()->object();returnnullptr;}// Eliminate checks which are redundant given each other or other instructions.//// A type barrier is considered redundant if all missing types have been tested// for by earlier control instructions.//// A bounds check is considered redundant if it's dominated by another bounds// check with the same length and the indexes differ by only a constant amount.// In this case we eliminate the redundant bounds check and update the other one// to cover the ranges of both checks.//// Bounds checks are added to a hash map and since the hash function ignores// differences in constant offset, this offers a fast way to find redundant// checks.booljit::EliminateRedundantChecks(MIRGraph&graph){BoundsCheckMapchecks(graph.alloc());if(!checks.init())returnfalse;// Stack for pre-order CFG traversal.Vector<MBasicBlock*,1,JitAllocPolicy>worklist(graph.alloc());// The index of the current block in the CFG traversal.size_tindex=0;// Add all self-dominating blocks to the worklist.// This includes all roots. Order does not matter.for(MBasicBlockIteratori(graph.begin());i!=graph.end();i++){MBasicBlock*block=*i;if(block->immediateDominator()==block){if(!worklist.append(block))returnfalse;}}MDefinitionVectoreliminateList(graph.alloc());// Starting from each self-dominating block, traverse the CFG in pre-order.while(!worklist.empty()){MBasicBlock*block=worklist.popCopy();// Add all immediate dominators to the front of the worklist.if(!worklist.append(block->immediatelyDominatedBlocksBegin(),block->immediatelyDominatedBlocksEnd())){returnfalse;}for(MDefinitionIteratoriter(block);iter;){MDefinition*def=*iter++;booleliminated=false;switch(def->op()){caseMDefinition::Op_BoundsCheck:if(!TryEliminateBoundsCheck(checks,index,def->toBoundsCheck(),&eliminated))returnfalse;break;caseMDefinition::Op_TypeBarrier:if(!TryEliminateTypeBarrier(def->toTypeBarrier(),&eliminated))returnfalse;break;caseMDefinition::Op_LoadFixedSlot:caseMDefinition::Op_LoadSlot:caseMDefinition::Op_LoadUnboxedObjectOrNull:if(!TryOptimizeLoadObjectOrNull(def,&eliminateList))returnfalse;break;default:// Now that code motion passes have finished, replace// instructions which pass through one of their operands// (and perform additional checks) with that operand.if(MDefinition*passthrough=PassthroughOperand(def))def->replaceAllUsesWith(passthrough);break;}if(eliminated)block->discardDef(def);}index++;}MOZ_ASSERT(index==graph.numBlocks());for(size_ti=0;i<eliminateList.length();i++){MDefinition*def=eliminateList[i];def->block()->discardDef(def);}returntrue;}staticboolNeedsKeepAlive(MInstruction*slotsOrElements,MInstruction*use){MOZ_ASSERT(slotsOrElements->type()==MIRType::Elements||slotsOrElements->type()==MIRType::Slots);if(slotsOrElements->block()!=use->block())returntrue;MBasicBlock*block=use->block();MInstructionIteratoriter(block->begin(slotsOrElements));MOZ_ASSERT(*iter==slotsOrElements);++iter;while(true){if(*iter==use)returnfalse;switch(iter->op()){caseMDefinition::Op_Nop:caseMDefinition::Op_Constant:caseMDefinition::Op_KeepAliveObject:caseMDefinition::Op_Unbox:caseMDefinition::Op_LoadSlot:caseMDefinition::Op_StoreSlot:caseMDefinition::Op_LoadFixedSlot:caseMDefinition::Op_StoreFixedSlot:caseMDefinition::Op_LoadElement:caseMDefinition::Op_StoreElement:caseMDefinition::Op_InitializedLength:caseMDefinition::Op_ArrayLength:caseMDefinition::Op_BoundsCheck:iter++;break;default:returntrue;}}MOZ_CRASH("Unreachable");}booljit::AddKeepAliveInstructions(MIRGraph&graph){for(MBasicBlockIteratori(graph.begin());i!=graph.end();i++){MBasicBlock*block=*i;for(MInstructionIteratorinsIter(block->begin());insIter!=block->end();insIter++){MInstruction*ins=*insIter;if(ins->type()!=MIRType::Elements&&ins->type()!=MIRType::Slots)continue;MDefinition*ownerObject;switch(ins->op()){caseMDefinition::Op_ConstantElements:continue;caseMDefinition::Op_ConvertElementsToDoubles:// EliminateRedundantChecks should have replaced all uses.MOZ_ASSERT(!ins->hasUses());continue;caseMDefinition::Op_Elements:caseMDefinition::Op_TypedArrayElements:caseMDefinition::Op_TypedObjectElements:MOZ_ASSERT(ins->numOperands()==1);ownerObject=ins->getOperand(0);break;caseMDefinition::Op_Slots:ownerObject=ins->toSlots()->object();break;default:MOZ_CRASH("Unexpected op");}MOZ_ASSERT(ownerObject->type()==MIRType::Object);if(ownerObject->isConstant()){// Constants are kept alive by other pointers, for instance// ImmGCPtr in JIT code.continue;}for(MUseDefIteratoruses(ins);uses;uses++){MInstruction*use=uses.def()->toInstruction();if(use->isStoreElementHole()){// StoreElementHole has an explicit object operand. If GVN// is disabled, we can get different unbox instructions with// the same object as input, so we check for that case.MOZ_ASSERT_IF(!use->toStoreElementHole()->object()->isUnbox()&&!ownerObject->isUnbox(),use->toStoreElementHole()->object()==ownerObject);continue;}if(use->isFallibleStoreElement()){// See StoreElementHole case above.MOZ_ASSERT_IF(!use->toFallibleStoreElement()->object()->isUnbox()&&!ownerObject->isUnbox(),use->toFallibleStoreElement()->object()==ownerObject);continue;}if(use->isInArray()){// See StoreElementHole case above.MOZ_ASSERT_IF(!use->toInArray()->object()->isUnbox()&&!ownerObject->isUnbox(),use->toInArray()->object()==ownerObject);continue;}if(!NeedsKeepAlive(ins,use))continue;if(!graph.alloc().ensureBallast())returnfalse;MKeepAliveObject*keepAlive=MKeepAliveObject::New(graph.alloc(),ownerObject);use->block()->insertAfter(use,keepAlive);}}}returntrue;}boolLinearSum::multiply(int32_tscale){for(size_ti=0;i<terms_.length();i++){if(!SafeMul(scale,terms_[i].scale,&terms_[i].scale))returnfalse;}returnSafeMul(scale,constant_,&constant_);}boolLinearSum::divide(uint32_tscale){MOZ_ASSERT(scale>0);for(size_ti=0;i<terms_.length();i++){if(terms_[i].scale%scale!=0)returnfalse;}if(constant_%scale!=0)returnfalse;for(size_ti=0;i<terms_.length();i++)terms_[i].scale/=scale;constant_/=scale;returntrue;}boolLinearSum::add(constLinearSum&other,int32_tscale/* = 1 */){for(size_ti=0;i<other.terms_.length();i++){int32_tnewScale=scale;if(!SafeMul(scale,other.terms_[i].scale,&newScale))returnfalse;if(!add(other.terms_[i].term,newScale))returnfalse;}int32_tnewConstant=scale;if(!SafeMul(scale,other.constant_,&newConstant))returnfalse;returnadd(newConstant);}boolLinearSum::add(SimpleLinearSumother,int32_tscale){if(other.term&&!add(other.term,scale))returnfalse;int32_tconstant;if(!SafeMul(other.constant,scale,&constant))returnfalse;returnadd(constant);}boolLinearSum::add(MDefinition*term,int32_tscale){MOZ_ASSERT(term);if(scale==0)returntrue;if(MConstant*termConst=term->maybeConstantValue()){int32_tconstant=termConst->toInt32();if(!SafeMul(constant,scale,&constant))returnfalse;returnadd(constant);}for(size_ti=0;i<terms_.length();i++){if(term==terms_[i].term){if(!SafeAdd(scale,terms_[i].scale,&terms_[i].scale))returnfalse;if(terms_[i].scale==0){terms_[i]=terms_.back();terms_.popBack();}returntrue;}}AutoEnterOOMUnsafeRegionoomUnsafe;if(!terms_.append(LinearTerm(term,scale)))oomUnsafe.crash("LinearSum::add");returntrue;}boolLinearSum::add(int32_tconstant){returnSafeAdd(constant,constant_,&constant_);}voidLinearSum::dump(GenericPrinter&out)const{for(size_ti=0;i<terms_.length();i++){int32_tscale=terms_[i].scale;int32_tid=terms_[i].term->id();MOZ_ASSERT(scale);if(scale>0){if(i)out.printf("+");if(scale==1)out.printf("#%d",id);elseout.printf("%d*#%d",scale,id);}elseif(scale==-1){out.printf("-#%d",id);}else{out.printf("%d*#%d",scale,id);}}if(constant_>0)out.printf("+%d",constant_);elseif(constant_<0)out.printf("%d",constant_);}voidLinearSum::dump()const{Fprinterout(stderr);dump(out);out.finish();}MDefinition*jit::ConvertLinearSum(TempAllocator&alloc,MBasicBlock*block,constLinearSum&sum,boolconvertConstant){MDefinition*def=nullptr;for(size_ti=0;i<sum.numTerms();i++){LinearTermterm=sum.term(i);MOZ_ASSERT(!term.term->isConstant());if(term.scale==1){if(def){def=MAdd::New(alloc,def,term.term);def->toAdd()->setInt32Specialization();block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}else{def=term.term;}}elseif(term.scale==-1){if(!def){def=MConstant::New(alloc,Int32Value(0));block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}def=MSub::New(alloc,def,term.term);def->toSub()->setInt32Specialization();block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}else{MOZ_ASSERT(term.scale!=0);MConstant*factor=MConstant::New(alloc,Int32Value(term.scale));block->insertAtEnd(factor);MMul*mul=MMul::New(alloc,term.term,factor);mul->setInt32Specialization();block->insertAtEnd(mul);mul->computeRange(alloc);if(def){def=MAdd::New(alloc,def,mul);def->toAdd()->setInt32Specialization();block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}else{def=mul;}}}if(convertConstant&&sum.constant()){MConstant*constant=MConstant::New(alloc,Int32Value(sum.constant()));block->insertAtEnd(constant);constant->computeRange(alloc);if(def){def=MAdd::New(alloc,def,constant);def->toAdd()->setInt32Specialization();block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}else{def=constant;}}if(!def){def=MConstant::New(alloc,Int32Value(0));block->insertAtEnd(def->toInstruction());def->computeRange(alloc);}returndef;}MCompare*jit::ConvertLinearInequality(TempAllocator&alloc,MBasicBlock*block,constLinearSum&sum){LinearSumlhs(sum);// Look for a term with a -1 scale which we can use for the rhs.MDefinition*rhsDef=nullptr;for(size_ti=0;i<lhs.numTerms();i++){if(lhs.term(i).scale==-1){AutoEnterOOMUnsafeRegionoomUnsafe;rhsDef=lhs.term(i).term;if(!lhs.add(rhsDef,1))oomUnsafe.crash("ConvertLinearInequality");break;}}MDefinition*lhsDef=nullptr;JSOpop=JSOP_GE;do{if(!lhs.numTerms()){lhsDef=MConstant::New(alloc,Int32Value(lhs.constant()));block->insertAtEnd(lhsDef->toInstruction());lhsDef->computeRange(alloc);break;}lhsDef=ConvertLinearSum(alloc,block,lhs);if(lhs.constant()==0)break;if(lhs.constant()==-1){op=JSOP_GT;break;}if(!rhsDef){int32_tconstant=lhs.constant();if(SafeMul(constant,-1,&constant)){rhsDef=MConstant::New(alloc,Int32Value(constant));block->insertAtEnd(rhsDef->toInstruction());rhsDef->computeRange(alloc);break;}}MDefinition*constant=MConstant::New(alloc,Int32Value(lhs.constant()));block->insertAtEnd(constant->toInstruction());constant->computeRange(alloc);lhsDef=MAdd::New(alloc,lhsDef,constant);lhsDef->toAdd()->setInt32Specialization();block->insertAtEnd(lhsDef->toInstruction());lhsDef->computeRange(alloc);}while(false);if(!rhsDef){rhsDef=MConstant::New(alloc,Int32Value(0));block->insertAtEnd(rhsDef->toInstruction());rhsDef->computeRange(alloc);}MCompare*compare=MCompare::New(alloc,lhsDef,rhsDef,op);block->insertAtEnd(compare);compare->setCompareType(MCompare::Compare_Int32);returncompare;}staticboolAnalyzePoppedThis(JSContext*cx,ObjectGroup*group,MDefinition*thisValue,MInstruction*ins,booldefinitelyExecuted,HandlePlainObjectbaseobj,Vector<TypeNewScript::Initializer>*initializerList,Vector<PropertyName*>*accessedProperties,bool*phandled){// Determine the effect that a use of the |this| value when calling |new|// on a script has on the properties definitely held by the new object.if(ins->isCallSetProperty()){MCallSetProperty*setprop=ins->toCallSetProperty();if(setprop->object()!=thisValue)returntrue;if(setprop->name()==cx->names().prototype||setprop->name()==cx->names().proto||setprop->name()==cx->names().constructor){returntrue;}// Ignore assignments to properties that were already written to.if(baseobj->lookup(cx,NameToId(setprop->name()))){*phandled=true;returntrue;}// Don't add definite properties for properties that were already// read in the constructor.for(size_ti=0;i<accessedProperties->length();i++){if((*accessedProperties)[i]==setprop->name())returntrue;}// Assignments to new properties must always execute.if(!definitelyExecuted)returntrue;RootedIdid(cx,NameToId(setprop->name()));if(!AddClearDefiniteGetterSetterForPrototypeChain(cx,group,id)){// The prototype chain already contains a getter/setter for this// property, or type information is too imprecise.returntrue;}// Add the property to the object, being careful not to update type information.DebugOnly<unsigned>slotSpan=baseobj->slotSpan();MOZ_ASSERT(!baseobj->containsPure(id));if(!NativeObject::addDataProperty(cx,baseobj,id,baseobj->slotSpan(),JSPROP_ENUMERATE))returnfalse;MOZ_ASSERT(baseobj->slotSpan()!=slotSpan);MOZ_ASSERT(!baseobj->inDictionaryMode());Vector<MResumePoint*>callerResumePoints(cx);for(MResumePoint*rp=ins->block()->callerResumePoint();rp;rp=rp->block()->callerResumePoint()){if(!callerResumePoints.append(rp))returnfalse;}for(inti=callerResumePoints.length()-1;i>=0;i--){MResumePoint*rp=callerResumePoints[i];JSScript*script=rp->block()->info().script();TypeNewScript::Initializerentry(TypeNewScript::Initializer::SETPROP_FRAME,script->pcToOffset(rp->pc()));if(!initializerList->append(entry))returnfalse;}JSScript*script=ins->block()->info().script();TypeNewScript::Initializerentry(TypeNewScript::Initializer::SETPROP,script->pcToOffset(setprop->resumePoint()->pc()));if(!initializerList->append(entry))returnfalse;*phandled=true;returntrue;}if(ins->isCallGetProperty()){MCallGetProperty*get=ins->toCallGetProperty();/* * Properties can be read from the 'this' object if the following hold: * * - The read is not on a getter along the prototype chain, which * could cause 'this' to escape. * * - The accessed property is either already a definite property or * is not later added as one. Since the definite properties are * added to the object at the point of its creation, reading a * definite property before it is assigned could incorrectly hit. */RootedIdid(cx,NameToId(get->name()));if(!baseobj->lookup(cx,id)&&!accessedProperties->append(get->name()))returnfalse;if(!AddClearDefiniteGetterSetterForPrototypeChain(cx,group,id)){// The |this| value can escape if any property reads it does go// through a getter.returntrue;}*phandled=true;returntrue;}if(ins->isPostWriteBarrier()){*phandled=true;returntrue;}returntrue;}staticintCmpInstructions(constvoid*a,constvoid*b){return(*static_cast<MInstruction*const*>(a))->id()-(*static_cast<MInstruction*const*>(b))->id();}booljit::AnalyzeNewScriptDefiniteProperties(JSContext*cx,HandleFunctionfun,ObjectGroup*group,HandlePlainObjectbaseobj,Vector<TypeNewScript::Initializer>*initializerList){MOZ_ASSERT(cx->zone()->types.activeAnalysis);// When invoking 'new' on the specified script, try to find some properties// which will definitely be added to the created object before it has a// chance to escape and be accessed elsewhere.RootedScriptscript(cx,JSFunction::getOrCreateScript(cx,fun));if(!script)returnfalse;if(!jit::IsIonEnabled(cx)||!jit::IsBaselineEnabled(cx)||!script->canBaselineCompile())returntrue;staticconstuint32_tMAX_SCRIPT_SIZE=2000;if(script->length()>MAX_SCRIPT_SIZE)returntrue;TraceLoggerThread*logger=TraceLoggerForCurrentThread(cx);TraceLoggerEventevent(TraceLogger_AnnotateScripts,script);AutoTraceLoglogScript(logger,event);AutoTraceLoglogCompile(logger,TraceLogger_IonAnalysis);Vector<PropertyName*>accessedProperties(cx);LifoAllocalloc(TempAllocator::PreferredLifoChunkSize);TempAllocatortemp(&alloc);JitContextjctx(cx,&temp);if(!jit::CanLikelyAllocateMoreExecutableMemory())returntrue;if(!cx->compartment()->ensureJitCompartmentExists(cx))returnfalse;if(!script->hasBaselineScript()){MethodStatusstatus=BaselineCompile(cx,script);if(status==Method_Error)returnfalse;if(status!=Method_Compiled)returntrue;}TypeScript::SetThis(cx,script,TypeSet::ObjectType(group));MIRGraphgraph(&temp);InlineScriptTree*inlineScriptTree=InlineScriptTree::New(&temp,nullptr,nullptr,script);if(!inlineScriptTree)returnfalse;CompileInfoinfo(script,fun,/* osrPc = */nullptr,Analysis_DefiniteProperties,script->needsArgsObj(),inlineScriptTree);constOptimizationInfo*optimizationInfo=IonOptimizations.get(OptimizationLevel::Normal);CompilerConstraintList*constraints=NewCompilerConstraintList(temp);if(!constraints){ReportOutOfMemory(cx);returnfalse;}BaselineInspectorinspector(script);constJitCompileOptionsoptions(cx);IonBuilderbuilder(cx,CompileCompartment::get(cx->compartment()),options,&temp,&graph,constraints,&inspector,&info,optimizationInfo,/* baselineFrame = */nullptr);AbortReasonOr<Ok>buildResult=builder.build();if(buildResult.isErr()){AbortReasonreason=buildResult.unwrapErr();if(cx->isThrowingOverRecursed()||cx->isThrowingOutOfMemory())returnfalse;if(reason==AbortReason::Alloc){ReportOutOfMemory(cx);returnfalse;}MOZ_ASSERT(!cx->isExceptionPending());returntrue;}FinishDefinitePropertiesAnalysis(cx,constraints);if(!SplitCriticalEdges(graph)){ReportOutOfMemory(cx);returnfalse;}RenumberBlocks(graph);if(!BuildDominatorTree(graph)){ReportOutOfMemory(cx);returnfalse;}if(!EliminatePhis(&builder,graph,AggressiveObservability)){ReportOutOfMemory(cx);returnfalse;}MDefinition*thisValue=graph.entryBlock()->getSlot(info.thisSlot());// Get a list of instructions using the |this| value in the order they// appear in the graph.Vector<MInstruction*>instructions(cx);for(MUseDefIteratoruses(thisValue);uses;uses++){MDefinition*use=uses.def();// Don't track |this| through assignments to phis.if(!use->isInstruction())returntrue;if(!instructions.append(use->toInstruction()))returnfalse;}// Sort the instructions to visit in increasing order.qsort(instructions.begin(),instructions.length(),sizeof(MInstruction*),CmpInstructions);// Find all exit blocks in the graph.Vector<MBasicBlock*>exitBlocks(cx);for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){if(!block->numSuccessors()&&!exitBlocks.append(*block))returnfalse;}// id of the last block which added a new property.size_tlastAddedBlock=0;for(size_ti=0;i<instructions.length();i++){MInstruction*ins=instructions[i];// Track whether the use of |this| is in unconditional code, i.e.// the block dominates all graph exits.booldefinitelyExecuted=true;for(size_ti=0;i<exitBlocks.length();i++){for(MBasicBlock*exit=exitBlocks[i];exit!=ins->block();exit=exit->immediateDominator()){if(exit==exit->immediateDominator()){definitelyExecuted=false;break;}}}// Also check to see if the instruction is inside a loop body. Even if// an access will always execute in the script, if it executes multiple// times then we can get confused when rolling back objects while// clearing the new script information.if(ins->block()->loopDepth()!=0)definitelyExecuted=false;boolhandled=false;size_tslotSpan=baseobj->slotSpan();if(!AnalyzePoppedThis(cx,group,thisValue,ins,definitelyExecuted,baseobj,initializerList,&accessedProperties,&handled)){returnfalse;}if(!handled)break;if(slotSpan!=baseobj->slotSpan()){MOZ_ASSERT(ins->block()->id()>=lastAddedBlock);lastAddedBlock=ins->block()->id();}}if(baseobj->slotSpan()!=0){// We found some definite properties, but their correctness is still// contingent on the correct frames being inlined. Add constraints to// invalidate the definite properties if additional functions could be// called at the inline frame sites.Vector<MBasicBlock*>exitBlocks(cx);for(MBasicBlockIteratorblock(graph.begin());block!=graph.end();block++){// Inlining decisions made after the last new property was added to// the object don't need to be frozen.if(block->id()>lastAddedBlock)break;if(MResumePoint*rp=block->callerResumePoint()){if(block->numPredecessors()==1&&block->getPredecessor(0)==rp->block()){JSScript*script=rp->block()->info().script();if(!AddClearDefiniteFunctionUsesInScript(cx,group,script,block->info().script()))returnfalse;}}}}returntrue;}staticboolArgumentsUseCanBeLazy(JSContext*cx,JSScript*script,MInstruction*ins,size_tindex,bool*argumentsContentsObserved){// We can read the frame's arguments directly for f.apply(x, arguments).if(ins->isCall()){if(*ins->toCall()->resumePoint()->pc()==JSOP_FUNAPPLY&&ins->toCall()->numActualArgs()==2&&index==MCall::IndexOfArgument(1)){*argumentsContentsObserved=true;returntrue;}}// arguments[i] can read fp->canonicalActualArg(i) directly.if(ins->isCallGetElement()&&index==0){*argumentsContentsObserved=true;returntrue;}// MGetArgumentsObjectArg needs to be considered as a use that allows laziness.if(ins->isGetArgumentsObjectArg()&&index==0)returntrue;// arguments.length length can read fp->numActualArgs() directly.// arguments.callee can read fp->callee() directly if the arguments object// is mapped.if(ins->isCallGetProperty()&&index==0&&(ins->toCallGetProperty()->name()==cx->names().length||(script->hasMappedArgsObj()&&ins->toCallGetProperty()->name()==cx->names().callee))){returntrue;}returnfalse;}booljit::AnalyzeArgumentsUsage(JSContext*cx,JSScript*scriptArg){RootedScriptscript(cx,scriptArg);AutoEnterAnalysisenter(cx);MOZ_ASSERT(!script->analyzedArgsUsage());// Treat the script as needing an arguments object until we determine it// does not need one. This both allows us to easily see where the arguments// object can escape through assignments to the function's named arguments,// and also simplifies handling of early returns.script->setNeedsArgsObj(true);// Always construct arguments objects when in debug mode, for generator// scripts (generators can be suspended when speculation fails) or when// direct eval is present.//// FIXME: Don't build arguments for ES6 generator expressions.if(scriptArg->isDebuggee()||script->isStarGenerator()||script->isLegacyGenerator()||script->isAsync()||script->bindingsAccessedDynamically()){returntrue;}if(!jit::IsIonEnabled(cx))returntrue;staticconstuint32_tMAX_SCRIPT_SIZE=10000;if(script->length()>MAX_SCRIPT_SIZE)returntrue;if(!script->ensureHasTypes(cx))returnfalse;TraceLoggerThread*logger=TraceLoggerForCurrentThread(cx);TraceLoggerEventevent(TraceLogger_AnnotateScripts,script);AutoTraceLoglogScript(logger,event);AutoTraceLoglogCompile(logger,TraceLogger_IonAnalysis);LifoAllocalloc(TempAllocator::PreferredLifoChunkSize);TempAllocatortemp(&alloc);JitContextjctx(cx,&temp);if(!jit::CanLikelyAllocateMoreExecutableMemory())returntrue;if(!cx->compartment()->ensureJitCompartmentExists(cx))returnfalse;MIRGraphgraph(&temp);InlineScriptTree*inlineScriptTree=InlineScriptTree::New(&temp,nullptr,nullptr,script);if(!inlineScriptTree){ReportOutOfMemory(cx);returnfalse;}CompileInfoinfo(script,script->functionNonDelazifying(),/* osrPc = */nullptr,Analysis_ArgumentsUsage,/* needsArgsObj = */true,inlineScriptTree);constOptimizationInfo*optimizationInfo=IonOptimizations.get(OptimizationLevel::Normal);CompilerConstraintList*constraints=NewCompilerConstraintList(temp);if(!constraints){ReportOutOfMemory(cx);returnfalse;}BaselineInspectorinspector(script);constJitCompileOptionsoptions(cx);IonBuilderbuilder(nullptr,CompileCompartment::get(cx->compartment()),options,&temp,&graph,constraints,&inspector,&info,optimizationInfo,/* baselineFrame = */nullptr);AbortReasonOr<Ok>buildResult=builder.build();if(buildResult.isErr()){AbortReasonreason=buildResult.unwrapErr();if(cx->isThrowingOverRecursed()||cx->isThrowingOutOfMemory())returnfalse;if(reason==AbortReason::Alloc){ReportOutOfMemory(cx);returnfalse;}MOZ_ASSERT(!cx->isExceptionPending());returntrue;}if(!SplitCriticalEdges(graph)){ReportOutOfMemory(cx);returnfalse;}RenumberBlocks(graph);if(!BuildDominatorTree(graph)){ReportOutOfMemory(cx);returnfalse;}if(!EliminatePhis(&builder,graph,AggressiveObservability)){ReportOutOfMemory(cx);returnfalse;}MDefinition*argumentsValue=graph.entryBlock()->getSlot(info.argsObjSlot());boolargumentsContentsObserved=false;for(MUseDefIteratoruses(argumentsValue);uses;uses++){MDefinition*use=uses.def();// Don't track |arguments| through assignments to phis.if(!use->isInstruction())returntrue;if(!ArgumentsUseCanBeLazy(cx,script,use->toInstruction(),use->indexOf(uses.use()),&argumentsContentsObserved)){returntrue;}}// If a script explicitly accesses the contents of 'arguments', and has// formals which may be stored as part of a call object, don't use lazy// arguments. The compiler can then assume that accesses through// arguments[i] will be on unaliased variables.if(script->funHasAnyAliasedFormal()&&argumentsContentsObserved)returntrue;script->setNeedsArgsObj(false);returntrue;}// Mark all the blocks that are in the loop with the given header.// Returns the number of blocks marked. Set *canOsr to true if the loop is// reachable from both the normal entry and the OSR entry.size_tjit::MarkLoopBlocks(MIRGraph&graph,MBasicBlock*header,bool*canOsr){#ifdef DEBUGfor(ReversePostorderIteratori=graph.rpoBegin(),e=graph.rpoEnd();i!=e;++i)MOZ_ASSERT(!i->isMarked(),"Some blocks already marked");#endifMBasicBlock*osrBlock=graph.osrBlock();*canOsr=false;// The blocks are in RPO; start at the loop backedge, which marks the bottom// of the loop, and walk up until we get to the header. Loops may be// discontiguous, so we trace predecessors to determine which blocks are// actually part of the loop. The backedge is always part of the loop, and// so are its predecessors, transitively, up to the loop header or an OSR// entry.MBasicBlock*backedge=header->backedge();backedge->mark();size_tnumMarked=1;for(PostorderIteratori=graph.poBegin(backedge);;++i){MOZ_ASSERT(i!=graph.poEnd(),"Reached the end of the graph while searching for the loop header");MBasicBlock*block=*i;// If we've reached the loop header, we're done.if(block==header)break;// A block not marked by the time we reach it is not in the loop.if(!block->isMarked())continue;// This block is in the loop; trace to its predecessors.for(size_tp=0,e=block->numPredecessors();p!=e;++p){MBasicBlock*pred=block->getPredecessor(p);if(pred->isMarked())continue;// Blocks dominated by the OSR entry are not part of the loop// (unless they aren't reachable from the normal entry).if(osrBlock&&pred!=header&&osrBlock->dominates(pred)&&!osrBlock->dominates(header)){*canOsr=true;continue;}MOZ_ASSERT(pred->id()>=header->id()&&pred->id()<=backedge->id(),"Loop block not between loop header and loop backedge");pred->mark();++numMarked;// A nested loop may not exit back to the enclosing loop at its// bottom. If we just marked its header, then the whole nested loop// is part of the enclosing loop.if(pred->isLoopHeader()){MBasicBlock*innerBackedge=pred->backedge();if(!innerBackedge->isMarked()){// Mark its backedge so that we add all of its blocks to the// outer loop as we walk upwards.innerBackedge->mark();++numMarked;// If the nested loop is not contiguous, we may have already// passed its backedge. If this happens, back up.if(innerBackedge->id()>block->id()){i=graph.poBegin(innerBackedge);--i;}}}}}// If there's no path connecting the header to the backedge, then this isn't// actually a loop. This can happen when the code starts with a loop but GVN// folds some branches away.if(!header->isMarked()){jit::UnmarkLoopBlocks(graph,header);return0;}returnnumMarked;}// Unmark all the blocks that are in the loop with the given header.voidjit::UnmarkLoopBlocks(MIRGraph&graph,MBasicBlock*header){MBasicBlock*backedge=header->backedge();for(ReversePostorderIteratori=graph.rpoBegin(header);;++i){MOZ_ASSERT(i!=graph.rpoEnd(),"Reached the end of the graph while searching for the backedge");MBasicBlock*block=*i;if(block->isMarked()){block->unmark();if(block==backedge)break;}}#ifdef DEBUGfor(ReversePostorderIteratori=graph.rpoBegin(),e=graph.rpoEnd();i!=e;++i)MOZ_ASSERT(!i->isMarked(),"Not all blocks got unmarked");#endif}// Reorder the blocks in the loop starting at the given header to be contiguous.staticvoidMakeLoopContiguous(MIRGraph&graph,MBasicBlock*header,size_tnumMarked){MBasicBlock*backedge=header->backedge();MOZ_ASSERT(header->isMarked(),"Loop header is not part of loop");MOZ_ASSERT(backedge->isMarked(),"Loop backedge is not part of loop");// If there are any blocks between the loop header and the loop backedge// that are not part of the loop, prepare to move them to the end. We keep// them in order, which preserves RPO.ReversePostorderIteratorinsertIter=graph.rpoBegin(backedge);insertIter++;MBasicBlock*insertPt=*insertIter;// Visit all the blocks from the loop header to the loop backedge.size_theaderId=header->id();size_tinLoopId=headerId;size_tnotInLoopId=inLoopId+numMarked;ReversePostorderIteratori=graph.rpoBegin(header);for(;;){MBasicBlock*block=*i++;MOZ_ASSERT(block->id()>=header->id()&&block->id()<=backedge->id(),"Loop backedge should be last block in loop");if(block->isMarked()){// This block is in the loop.block->unmark();block->setId(inLoopId++);// If we've reached the loop backedge, we're done!if(block==backedge)break;}else{// This block is not in the loop. Move it to the end.graph.moveBlockBefore(insertPt,block);block->setId(notInLoopId++);}}MOZ_ASSERT(header->id()==headerId,"Loop header id changed");MOZ_ASSERT(inLoopId==headerId+numMarked,"Wrong number of blocks kept in loop");MOZ_ASSERT(notInLoopId==(insertIter!=graph.rpoEnd()?insertPt->id():graph.numBlocks()),"Wrong number of blocks moved out of loop");}// Reorder the blocks in the graph so that loops are contiguous.booljit::MakeLoopsContiguous(MIRGraph&graph){// Visit all loop headers (in any order).for(MBasicBlockIteratori(graph.begin());i!=graph.end();i++){MBasicBlock*header=*i;if(!header->isLoopHeader())continue;// Mark all blocks that are actually part of the loop.boolcanOsr;size_tnumMarked=MarkLoopBlocks(graph,header,&canOsr);// If the loop isn't a loop, don't try to optimize it.if(numMarked==0)continue;// If there's an OSR block entering the loop in the middle, it's tricky,// so don't try to handle it, for now.if(canOsr){UnmarkLoopBlocks(graph,header);continue;}// Move all blocks between header and backedge that aren't marked to// the end of the loop, making the loop itself contiguous.MakeLoopContiguous(graph,header,numMarked);}returntrue;}MRootList::MRootList(TempAllocator&alloc){#define INIT_VECTOR(name, _0, _1) \ roots_[JS::RootKind::name].emplace(alloc);JS_FOR_EACH_TRACEKIND(INIT_VECTOR)#undef INIT_VECTOR}template<typenameT>staticvoidTraceVector(JSTracer*trc,constMRootList::RootVector&vector,constchar*name){for(autoptr:vector){TptrT=static_cast<T>(ptr);TraceManuallyBarrieredEdge(trc,&ptrT,name);MOZ_ASSERT(ptr==ptrT,"Shouldn't move without updating MIR pointers");}}voidMRootList::trace(JSTracer*trc){#define TRACE_ROOTS(name, type, _) \ TraceVector<type*>(trc, *roots_[JS::RootKind::name], "mir-root-" #name);JS_FOR_EACH_TRACEKIND(TRACE_ROOTS)#undef TRACE_ROOTS}MOZ_MUST_USEbooljit::CreateMIRRootList(IonBuilder&builder){MOZ_ASSERT(!builder.info().isAnalysis());TempAllocator&alloc=builder.alloc();MIRGraph&graph=builder.graph();MRootList*roots=new(alloc.fallible())MRootList(alloc);if(!roots)returnfalse;JSScript*prevScript=nullptr;for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++){JSScript*script=block->info().script();if(script!=prevScript){if(!roots->append(script))returnfalse;prevScript=script;}for(MInstructionIteratoriter(block->begin()),end(block->end());iter!=end;iter++){if(!iter->appendRoots(*roots))returnfalse;}}builder.setRootList(*roots);returntrue;}staticvoidDumpDefinition(GenericPrinter&out,MDefinition*def,size_tdepth){MDefinition::PrintOpcodeName(out,def->op());if(depth==0)return;for(size_ti=0;i<def->numOperands();i++){out.printf(" (");DumpDefinition(out,def->getOperand(i),depth-1);out.printf(")");}}voidjit::DumpMIRExpressions(MIRGraph&graph){if(!JitSpewEnabled(JitSpew_MIRExpressions))return;size_tdepth=2;Fprinter&out=JitSpewPrinter();for(ReversePostorderIteratorblock(graph.rpoBegin());block!=graph.rpoEnd();block++){for(MInstructionIteratoriter(block->begin()),end(block->end());iter!=end;iter++){DumpDefinition(out,*iter,depth);out.printf("\n");}}}